A DETERMINISTIC POLYNOMIAL-TIME APPROXIMATION SCHEME FOR COUNTING KNAPSACK SOLUTIONS

作者：Stefankovic Daniel^*; Vempala Santosh; Vigoda Eric

来源：SIAM Journal on Computing, 2012, 41(2): 356-366.

DOI：10.1137/11083976X

• approximate counting
• knapsack
• dynamic programming

Given n elements with nonnegative integer weights w(1),..., 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 +/-epsilon in time polynomial in n and 1/epsilon ( fully polynomial approximation scheme). More precisely, our algorithm takes time O(n(3)epsilon(-1) log(n/epsilon)). 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.

• 出版日期2012