Faster FPTASes for counting and random generation of Knapsack solutions

Show simple item record

dc.contributor University of Helsinki, Department of Computer Science en Rizzi, Romeo Tomescu, Alexandru I. 2019-06-07T09:10:02Z 2019-06-07T09:10:02Z 2019-08
dc.identifier.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 . en
dc.identifier.issn 0890-5401
dc.identifier.other PURE: 123956536
dc.identifier.other PURE UUID: 8c560bfd-3dd8-4245-8ebe-64db8f6dbcd3
dc.identifier.other RIS: urn:35F98EE0E5A99D9F5FEC8824937363B1
dc.identifier.other WOS: 000468202000008
dc.identifier.other ORCID: /0000-0002-5747-8350/work/58267217
dc.description.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. en
dc.format.extent 10
dc.language.iso eng
dc.relation.ispartof Information and Computation
dc.rights en
dc.subject 0/1 Knapsack problem en
dc.subject Approximation algorithm en
dc.subject Counting problem en
dc.subject Sampling en
dc.subject Dynamic programming en
dc.subject Directed acyclic graph en
dc.subject 113 Computer and information sciences en
dc.title Faster FPTASes for counting and random generation of Knapsack solutions en
dc.type Article
dc.description.version Peer reviewed
dc.type.uri info:eu-repo/semantics/other
dc.type.uri info:eu-repo/semantics/publishedVersion

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 simple item record