A Faster FPTAS for #Knapsack

Given a set W = w1,ldots, wn 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 u1,ldots, un and we are allowed to take up to ui items of weight wi. We present a deterministic FPTAS for #Knapsack running in O(n2.5varepsilon-1.5log(n varepsilon-1)log (n varepsilon)) time. The previous best deterministic algorithm [FOCS 2011] runs in O(n3 varepsilon-1 log(nvarepsilon-1)) time (see also [ESA 2014] for a logarithmic factor improvement). The previous best randomized algorithm [STOC 2003] runs in O(n2.5 √log (nvarepsilon-1) + varepsilon-2 n2 ) time. Therefore, in the natural setting of constant varepsilon, we close the gap between the tilde O(n2.5) randomized algorithm and the tilde O(n3) deterministic algorithm. For the integer version with U = maxi ui, we present a deterministic FPTAS running in O(n2.5varepsilon-1.5log(nvarepsilon-1 log U)log (n varepsilon) log2 U) time. The previous best deterministic algorithm [APPROX 2016] runs in O(n3varepsilon-1log(n varepsilon-1 log U) log2 U) time.