Faster FPTASes for counting and random generation of Knapsack solutions

Show full item record



Permalink

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

Title: Faster FPTASes for counting and random generation of Knapsack solutions
Author: Rizzi, Romeo; Tomescu, Alexandru I.
Contributor: University of Helsinki, Department of Computer Science
Date: 2019-08
Language: eng
Number of pages: 10
Belongs to series: Information and Computation
ISSN: 0890-5401
URI: http://hdl.handle.net/10138/302575
Abstract: 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
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
1_s2.0_S0890540119300276_main.pdf 384.0Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record