- A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy Nir Halman (halmanhuji.ac.il) Abstract: Given $n$ elements with nonnegative integer weights $w=(w_1,\ldots,w_n)$, an integer capacity $C$ and positive integer ranges $u=(u_1,\ldots,u_n)$, we consider the counting version of the classic integer knapsack problem: find the number of distinct multisets whose weights add up to at most $C$. We give a deterministic algorithm that estimates the number of solutions to within relative error $\eps$ in time polynomial in $n, \log U$ and $1/\eps$, where $U=\max_i u_i$. More precisely, our algorithm runs in $O(\frac{n^3 \log^2 U}{\eps} \log \frac{n \log U}{\eps})$ time. This is an improvement of $n^2$ and $1/\eps$ (up to log terms) over the best known deterministic algorithm by Gopalan {\em et al.} [FOCS, (2011), pp. 817-826]. Our algorithm is relatively simple, and its analysis is rather elementary. Our results are achieved by means of a careful formulation of the problem as a dynamic program, using the notion of {\em binding constraints}. Keywords: Approximate counting, integer knapsack, dynamic programming Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Other Topics (Dynamic Programming ) Citation: Technical Report, Hebrew University of Jerudalem Download: [PDF]Entry Submitted: 12/03/2015Entry Accepted: 12/03/2015Entry Last Modified: 07/03/2016Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.