A Faster FPTAS for #Knapsack

Abstract

Given a set $W=\{w_1,\dots ,w_n\}$ of non-negative integer weights and an integer $C$, the #Knapsack problem asks to count the number of distinct subsets of $W$ whose total weight is at most $C$. In the more general integer version of the problem, the subsets are multisets. That is, we are also given a set $\{u_1,\dots ,u_n\}$ and we are allowed to take up to $u_i$ items of weight $w_i$. We present a deterministic FPTAS for #Knapsack running in $O(n^{2.5}{\epsilon }^{-1.5}\log (n{\epsilon }^{-1})\log (n\epsilon ))$ time. The previous best deterministic algorithm [FOCS 2011] runs in $O(n^3{\epsilon }^{-1}\log (n{\epsilon }^{-1}))$ time (see also [ESA 2014] for a logarithmic factor improvement). The previous best randomized algorithm [STOC 2003] runs in $O(n^{2.5}\sqrt{\log (n{\epsilon }^{-1})}+{\epsilon }^{-2}{n}^2)$ time. Therefore, in the natural setting of constant $\epsilon$, we close the gap between the $\tilde{O}(n^{2.5})$ randomized algorithm and the $\tilde{O}(n^3)$ deterministic algorithm. For the integer version with $U={\max }_i\{u_i\}$, we present a deterministic FPTAS running in $O(n^{2.5}{\epsilon }^{-1.5}\log (n{\epsilon }^{-1}\log U)\log (n\epsilon ){\log }^{2}U)$ time. The previous best deterministic algorithm [APPROX 2016] runs in $O(n^3{\epsilon }^{-1}\log (n{\epsilon }^{-1}\log U){\log }^{2}U)$ time.