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å värdpublikation | 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 | |
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