### Abstract

Original language | English |
---|---|

Journal | Information and Computation |

Volume | 267 |

Pages (from-to) | 135-144 |

Number of pages | 10 |

ISSN | 0890-5401 |

DOIs | |

Publication status | Published - Aug 2019 |

MoE publication type | A1 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

}

*Information and Computation*, vol. 267, pp. 135-144. https://doi.org/10.1016/j.ic.2019.04.001

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

Research output: Contribution to journal › Article › Scientific › peer-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 -