Faster FPTASes for Counting and Random Generation of Knapsack Solutions

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

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.
Alkuperäiskielienglanti
OtsikkoAlgorithms - ESA 2014 : 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings
ToimittajatAndreas S. Schulz, Dorothea Wagner
Sivumäärä12
KustantajaSpringer-Verlag
Julkaisupäivä2014
Sivut762-773
ISBN (painettu)978-3-662-44776-5
ISBN (elektroninen)978-3-662-44776-5
DOI - pysyväislinkit
TilaJulkaistu - 2014
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaEuropean Symposia on Algorithms - Wroclaw, Puola
Kesto: 8 syyskuuta 201410 syyskuuta 2014
Konferenssinumero: 22

Julkaisusarja

NimiLecture Notes in Computer Science
KustantajaSpringer
Vuosikerta8737
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349

Lisätietoja


Volume:
Proceeding volume:

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä