Faster FPTASes for Counting and Random Generation of Knapsack Solutions

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


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
Publication date2014
ISBN (Print)978-3-662-44776-5
ISBN (Electronic)978-3-662-44776-5
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
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fields of Science

  • 113 Computer and information sciences

Cite this