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

Forskningsoutput: Kapitel i bok/rapport/konferenshandling › Konferensbidrag › Vetenskaplig › Peer review

Sammanfattning

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.

Originalspråk	engelska
Titel på gästpublikation	Algorithms - ESA 2014 : 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings
Redaktörer	Andreas S. Schulz, Dorothea Wagner
Antal sidor	12
Förlag	Springer-Verlag
Utgivningsdatum	2014
Sidor	762-773
ISBN (tryckt)	978-3-662-44776-5
ISBN (elektroniskt)	978-3-662-44776-5
DOI	https://doi.org/10.1007/978-3-662-44777-2_63
Status	Publicerad - 2014
MoE-publikationstyp	A4 Artikel i en konferenspublikation
Evenemang	European Symposia on Algorithms - Wroclaw, Polen Varaktighet: 8 sep 2014 → 10 sep 2014 Konferensnummer: 22

Publikationsserier

Namn	Lecture Notes in Computer Science
Förlag	Springer
Volym	8737
ISSN (tryckt)	0302-9743
ISSN (elektroniskt)	1611-3349

Vetenskapsgrenar

113 Data- och informationsvetenskap

Åtkomst av dokument

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

http://esa-symposium.org/

Citera det här

Rizzi, R., & Tomescu, A. I. (2014). Faster FPTASes for Counting and Random Generation of Knapsack Solutions. I A. S. Schulz, & D. Wagner (Red.), Algorithms - ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings (s. 762-773). (Lecture Notes in Computer Science; Vol. 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.}",

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

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",

}

Rizzi, R & Tomescu, AI 2014, Faster FPTASes for Counting and Random Generation of Knapsack Solutions. i AS Schulz & D Wagner (red), Algorithms - ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings. Lecture Notes in Computer Science, vol. 8737, Springer-Verlag, s. 762-773, European Symposia on Algorithms, Wroclaw, Polen, 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. red. / Andreas S. Schulz; Dorothea Wagner. Springer-Verlag, 2014. s. 762-773 (Lecture Notes in Computer Science; Vol. 8737).

Forskningsoutput: Kapitel i bok/rapport/konferenshandling › Konferensbidrag › Vetenskaplig › Peer review

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 -