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