A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy

Given n elements with nonnegative integer weights w = ( w 1, …, w n ), an integer capacity C and positive integer ranges u = ( u 1, …, 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 ϵ in time polynomial in n, log ⁡ U and 1 / ϵ, where U = max i ⁡ u i. More precisely, our algorithm runs in O ( n 3 log 2 ⁡ U ϵ log ⁡ n log ⁡ U ϵ ) time. This is an improvement of n 2 and 1 / ϵ (up to log terms) over the best known deterministic algorithm by Gopalan et al. (2011) [5]. 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 binding constraints.

Authors

• Nir Halman

Keywords

• Approximate counting
• Integer knapsack
• Dynamic programming
• Binding constraints
• K-approximating sets and functions