  


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. 817826]. 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/2015 Modify/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  