Name
Abstract | ||
|---|---|---|
Given $n$ elements with nonnegative integer weights $w_1, \ldots, w_n$ and an integer capacity $C$, we consider the counting version of the classic knapsack problem: find the number of distinct subsets whose weights add up to at most the given capacity. We give a deterministic algorithm that estimates the number of solutions to within relative error $1\pm\varepsilon$ in time polynomial in $n$ and $1/\varepsilon$ (fully polynomial approximation scheme). More precisely, our algorithm takes time $O(n^3\varepsilon^{-1}\log(n/\varepsilon))$. Our algorithm is based on dynamic programming. Previously, randomized polynomial-time approximation schemes were known first by Morris and Sinclair via Markov chain Monte Carlo techniques and subsequently by Dyer via dynamic programming and rejection sampling. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/11083976X | Clinical Orthopaedics and Related Research |
Keywords | Field | DocType |
deterministic polynomial-time approximation scheme,classic knapsack problem,randomized polynomial-time approximation scheme,time polynomial,deterministic algorithm,knapsack solutions,polynomial approximation scheme,integer capacity,nonnegative integer weight,monte carlo technique,markov chain,dynamic programming,knapsack | Integer,Discrete mathematics,Rejection sampling,Combinatorics,Polynomial,Continuous knapsack problem,Deterministic algorithm,Knapsack problem,Polynomial-time approximation scheme,Mathematics,Approximation error | Journal |
Volume | Issue | ISSN |
41 | 2 | 0097-5397 |
Citations | PageRank | References |
13 | 0.72 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Štefankovič | 1 | 201 | 16.34 |
| Santosh Vempala | 2 | 3546 | 523.21 |
| Eric Vigoda | 3 | 747 | 76.55 |