Faster FPTASes for counting and random generation of Knapsack solutions

Research output: Contribution to journalArticleScientificpeer-review

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.
Original languageEnglish
JournalInformation and Computation
Volume267
Pages (from-to)135-144
Number of pages10
ISSN0890-5401
DOIs
Publication statusPublished - Aug 2019
MoE publication typeA1 Journal article-refereed

Fields of Science

  • 0/1 Knapsack problem
  • Approximation algorithm
  • Counting problem
  • Sampling
  • Dynamic programming
  • Directed acyclic graph
  • 113 Computer and information sciences

Cite this

@article{8c560bfd3dd842458ebe64db8f6dbcd3,
title = "Faster FPTASes for counting and random generation of Knapsack solutions",
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.",
keywords = "0/1 Knapsack problem, Approximation algorithm, Counting problem, Sampling, Dynamic programming, Directed acyclic graph, 113 Computer and information sciences",
author = "Romeo Rizzi and Tomescu, {Alexandru I.}",
year = "2019",
month = "8",
doi = "10.1016/j.ic.2019.04.001",
language = "English",
volume = "267",
pages = "135--144",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "ACADEMIC PRESS INC ELSEVIER SCIENCE",

}

Faster FPTASes for counting and random generation of Knapsack solutions. / Rizzi, Romeo; Tomescu, Alexandru I.

In: Information and Computation, Vol. 267, 08.2019, p. 135-144.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Faster FPTASes for counting and random generation of Knapsack solutions

AU - Rizzi, Romeo

AU - Tomescu, Alexandru I.

PY - 2019/8

Y1 - 2019/8

N2 - 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.

AB - 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.

KW - 0/1 Knapsack problem

KW - Approximation algorithm

KW - Counting problem

KW - Sampling

KW - Dynamic programming

KW - Directed acyclic graph

KW - 113 Computer and information sciences

U2 - 10.1016/j.ic.2019.04.001

DO - 10.1016/j.ic.2019.04.001

M3 - Article

VL - 267

SP - 135

EP - 144

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

ER -