Faster FPTASes for counting and random generation of Knapsack solutions

Visa fullständig post



Permalänk

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

Citation

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

Titel: Faster FPTASes for counting and random generation of Knapsack solutions
Författare: Rizzi, Romeo; Tomescu, Alexandru I.
Medarbetare: University of Helsinki, Department of Computer Science
Datum: 2019-08
Språk: eng
Sidantal: 10
Tillhör serie: Information and Computation
ISSN: 0890-5401
Permanenta länken (URI): http://hdl.handle.net/10138/302575
Abstrakt: 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.
Subject: 0/1 Knapsack problem
Approximation algorithm
Counting problem
Sampling
Dynamic programming
Directed acyclic graph
113 Computer and information sciences
Licens:


Filer under denna titel

Totalt antal nerladdningar: Laddar...

Filer Storlek Format Granska
1_s2.0_S0890540119300276_main.pdf 384.0Kb PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post