Faster FPTASes for counting and random generation of Knapsack solutions

Näytä kaikki kuvailutiedot



Pysyväisosoite

http://hdl.handle.net/10138/302575

Lähdeviite

Rizzi , R & Tomescu , A I 2019 , ' Faster FPTASes for counting and random generation of Knapsack solutions ' , Information and Computation , vol. 267 , pp. 135-144 . https://doi.org/10.1016/j.ic.2019.04.001

Julkaisun nimi: Faster FPTASes for counting and random generation of Knapsack solutions
Tekijä: Rizzi, Romeo; Tomescu, Alexandru I.
Muu tekijä: University of Helsinki, Department of Computer Science
Päiväys: 2019-08
Kieli: eng
Sivumäärä: 10
Kuuluu julkaisusarjaan: Information and Computation
ISSN: 0890-5401
URI: http://hdl.handle.net/10138/302575
Tiivistelmä: In the #P-complete problem of counting 0/1 Knapsack solutions, the input consists of a sequence of n nonnegative integer weights w1,…,wn and an integer C, and we have to find the number of subsequences (subsets of indices) with total weight at most C. We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for this problem, 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 from Gopalan et al. (2011) [9], Štefankovič et al. (2012) [6] and the randomized counting and random generation algorithms in Dyer (2003) [5]. Our method is general, and it can be directly applied on top of combinatorial decompositions (such as dynamic programming solutions) of various problems. For example, we also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG.
Avainsanat: 0/1 Knapsack problem
Approximation algorithm
Counting problem
Sampling
Dynamic programming
Directed acyclic graph
113 Computer and information sciences
Tekijänoikeustiedot:


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
1_s2.0_S0890540119300276_main.pdf 384.0KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot