Faster FPTASes for Counting and Random Generation of Knapsack Solutions

Romeo Rizzi; Alexandru I. Tomescu

doi:10.1007/978-3-662-44777-2_63

Faster FPTASes for Counting and Random Generation of Knapsack Solutions

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

Abstrakti

We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for the #P-complete problem of counting 0/1 Knapsack solutions, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes in (Gopalan et al., FOCS 2011), (Štefankovič et al., SIAM J. Comput. 2012) and the randomized counting and random generation algorithms in (Dyer, STOC 2003). We also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG.

Alkuperäiskieli	englanti
Otsikko	Algorithms - ESA 2014 : 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings
Toimittajat	Andreas S. Schulz, Dorothea Wagner
Sivumäärä	12
Kustantaja	Springer-Verlag
Julkaisupäivä	2014
Sivut	762-773
ISBN (painettu)	978-3-662-44776-5
ISBN (elektroninen)	978-3-662-44776-5
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-662-44777-2_63
Tila	Julkaistu - 2014
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	European Symposia on Algorithms - Wroclaw, Puola Kesto: 8 syysk. 2014 → 10 syysk. 2014 Konferenssinumero: 22

Julkaisusarja

Nimi	Lecture Notes in Computer Science
Kustantaja	Springer
Vuosikerta	8737
ISSN (painettu)	0302-9743
ISSN (elektroninen)	1611-3349

Tieteenalat

113 Tietojenkäsittely- ja informaatiotieteet

Pääsy asiakirjaan

10.1007/978-3-662-44777-2_63

http://esa-symposium.org/

Siteeraa tätä

Rizzi, R., & Tomescu, A. I. (2014). Faster FPTASes for Counting and Random Generation of Knapsack Solutions. teoksessa A. S. Schulz, & D. Wagner (Toimittajat), Algorithms - ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings (Sivut 762-773). (Lecture Notes in Computer Science; Vuosikerta 8737). Springer-Verlag. https://doi.org/10.1007/978-3-662-44777-2_63

@inproceedings{c6e846cb058145d9a4c52c481c5fa1b8,

title = "Faster FPTASes for Counting and Random Generation of Knapsack Solutions",

abstract = "We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for the #P-complete problem of counting 0/1 Knapsack solutions, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes in (Gopalan et al., FOCS 2011), ({\v S}tefankovi{\v c} et al., SIAM J. Comput. 2012) and the randomized counting and random generation algorithms in (Dyer, STOC 2003). We also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG.",

keywords = "113 Computer and information sciences",

author = "Romeo Rizzi and Tomescu, {Alexandru I.}",

year = "2014",

doi = "10.1007/978-3-662-44777-2_63",

language = "English",

isbn = "978-3-662-44776-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer-Verlag",

pages = "762--773",

editor = "Schulz, {Andreas S.} and Dorothea Wagner",

booktitle = "Algorithms - ESA 2014",

address = "Germany",

note = "European Symposia on Algorithms ; Conference date: 08-09-2014 Through 10-09-2014",

}

Rizzi, R & Tomescu, AI 2014, Faster FPTASes for Counting and Random Generation of Knapsack Solutions. julkaisussa AS Schulz & D Wagner (toim), Algorithms - ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings. Lecture Notes in Computer Science, Vuosikerta 8737, Springer-Verlag, Sivut 762-773, European Symposia on Algorithms, Wroclaw, Puola, 08/09/2014. https://doi.org/10.1007/978-3-662-44777-2_63

Faster FPTASes for Counting and Random Generation of Knapsack Solutions. / Rizzi, Romeo; Tomescu, Alexandru I.

Algorithms - ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings. toim. / Andreas S. Schulz; Dorothea Wagner. Springer-Verlag, 2014. s. 762-773 (Lecture Notes in Computer Science; Vuosikerta 8737).

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

TY - GEN

T1 - Faster FPTASes for Counting and Random Generation of Knapsack Solutions

AU - Rizzi, Romeo

AU - Tomescu, Alexandru I.

N1 - Conference code: 22

PY - 2014

Y1 - 2014

N2 - We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for the #P-complete problem of counting 0/1 Knapsack solutions, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes in (Gopalan et al., FOCS 2011), (Štefankovič et al., SIAM J. Comput. 2012) and the randomized counting and random generation algorithms in (Dyer, STOC 2003). We also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG.

AB - We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for the #P-complete problem of counting 0/1 Knapsack solutions, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes in (Gopalan et al., FOCS 2011), (Štefankovič et al., SIAM J. Comput. 2012) and the randomized counting and random generation algorithms in (Dyer, STOC 2003). We also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG.

KW - 113 Computer and information sciences

U2 - 10.1007/978-3-662-44777-2_63

DO - 10.1007/978-3-662-44777-2_63

M3 - Conference contribution

SN - 978-3-662-44776-5

T3 - Lecture Notes in Computer Science

SP - 762

EP - 773

BT - Algorithms - ESA 2014

A2 - Schulz, Andreas S.

A2 - Wagner, Dorothea

PB - Springer-Verlag

T2 - European Symposia on Algorithms

Y2 - 8 September 2014 through 10 September 2014

ER -