Faster FPTASes for Counting and Random Generation of Knapsack Solutions

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

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), (Š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.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2014 : 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings
EditorsAndreas S. Schulz, Dorothea Wagner
Number of pages12
PublisherSpringer-Verlag
Publication date2014
Pages762-773
ISBN (Print)978-3-662-44776-5
ISBN (Electronic)978-3-662-44776-5
DOIs
Publication statusPublished - 2014
MoE publication typeA4 Article in conference proceedings
EventEuropean Symposia on Algorithms - Wroclaw, Poland
Duration: 8 Sep 201410 Sep 2014
Conference number: 22

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8737
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fields of Science

  • 113 Computer and information sciences

Cite this

Rizzi, R., & Tomescu, A. I. (2014). Faster FPTASes for Counting and Random Generation of Knapsack Solutions. In A. S. Schulz, & D. Wagner (Eds.), Algorithms - ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings (pp. 762-773). (Lecture Notes in Computer Science; Vol. 8737). Springer-Verlag. https://doi.org/10.1007/978-3-662-44777-2_63
Rizzi, Romeo ; Tomescu, Alexandru I. / Faster FPTASes for Counting and Random Generation of Knapsack Solutions. Algorithms - ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings. editor / Andreas S. Schulz ; Dorothea Wagner. Springer-Verlag, 2014. pp. 762-773 (Lecture Notes in Computer Science).
@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), (Š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.",
keywords = "113 Computer and information sciences",
author = "Romeo Rizzi and Tomescu, {Alexandru I.}",
note = "Volume: Proceeding volume:",
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. in AS Schulz & D Wagner (eds), Algorithms - ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings. Lecture Notes in Computer Science, vol. 8737, Springer-Verlag, pp. 762-773, European Symposia on Algorithms, Wroclaw, Poland, 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. ed. / Andreas S. Schulz; Dorothea Wagner. Springer-Verlag, 2014. p. 762-773 (Lecture Notes in Computer Science; Vol. 8737).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

TY - GEN

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

AU - Rizzi, Romeo

AU - Tomescu, Alexandru I.

N1 - Volume: Proceeding volume:

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

ER -

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