Optimization Online


A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy

Nir Halman (halman***at***huji.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/2015
Entry Accepted: 12/03/2015
Entry Last Modified: 07/03/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society