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 language | English |
|---|---|
| Title of host publication | Algorithms - ESA 2014 : 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings |
| Editors | Andreas S. Schulz, Dorothea Wagner |
| Number of pages | 12 |
| Publisher | Springer-Verlag |
| Publication date | 2014 |
| Pages | 762-773 |
| ISBN (Print) | 978-3-662-44776-5 |
| ISBN (Electronic) | 978-3-662-44776-5 |
| DOIs | |
| Publication status | Published - 2014 |
| MoE publication type | A4 Article in conference proceedings |
| Event | European Symposia on Algorithms - Wroclaw, Poland Duration: 8 Sep 2014 → 10 Sep 2014 Conference number: 22 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 8737 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Fields of Science
- 113 Computer and information sciences