Faster FPTASes for Counting and Random Generation of Knapsack Solutions

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review

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åkengelska
Titel på värdpublikationAlgorithms - ESA 2014 : 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings
RedaktörerAndreas S. Schulz, Dorothea Wagner
Antal sidor12
FörlagSpringer-Verlag
Utgivningsdatum2014
Sidor762-773
ISBN (tryckt)978-3-662-44776-5
ISBN (elektroniskt)978-3-662-44776-5
DOI
StatusPublicerad - 2014
MoE-publikationstypA4 Artikel i en konferenspublikation
EvenemangEuropean Symposia on Algorithms - Wroclaw, Polen
Varaktighet: 8 sep. 201410 sep. 2014
Konferensnummer: 22

Publikationsserier

NamnLecture Notes in Computer Science
FörlagSpringer
Volym8737
ISSN (tryckt)0302-9743
ISSN (elektroniskt)1611-3349

Vetenskapsgrenar

  • 113 Data- och informationsvetenskap

Citera det här