A Faster FPTAS for #Knapsack

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 \varepsilon^{-1} \log(n\varepsilon^{-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\varepsilon^{-1}) } + \varepsilon^{-2} n^2 )$time\mathrm{.}Therefore,inthenaturalsettingofconstant$\varepsilon$, 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}\varepsilon^{-1.5}\log(n\varepsilon^{-1} \log U)\log (n \varepsilon) \log^2 U)$ time. The previous best deterministic algorithm [APPROX 2016] runs in $O(n^3\varepsilon^{-1}\log(n \varepsilon^{-1} \log U) \log^2 U)$ time.