A Faster FPTAS for #Knapsack
A Faster FPTAS for #Knapsack
复制标题
更快的 FPTAS
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Oren Weimann
中科院分区：
文献类型：
--
作者：
Paweł Gawrychowski;Liran Markin;Oren Weimann
Given a set $W = {w_1,ldots, 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,ldots, 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}varepsilon^{-1.5}log(n varepsilon^{-1})log (n varepsilon))$ time. The previous best deterministic algorithm [FOCS 2011] runs in $O(n^3 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(n^{2.5} sqrt{log (nvarepsilon^{-1}) } + varepsilon^{-2} n^2 )$ time. Therefore, in the natural setting of constant $varepsilon$, we close the gap between the $ ilde O(n^{2.5})$ randomized algorithm and the $ ilde 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(nvarepsilon^{-1} log U)log (n varepsilon) log^2 U)$ time. The previous best deterministic algorithm [APPROX 2016] runs in $O(n^3varepsilon^{-1}log(n varepsilon^{-1} log U) log^2 U)$ time.
Given a set $W = {w_1,ldots, 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,ldots, 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}varepsilon^{-1.5}log(n varepsilon^{-1})log (n varepsilon))$ time. The previous best deterministic algorithm [FOCS 2011] runs in $O(n^3 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(n^{2.5} sqrt{log (nvarepsilon^{-1}) } + varepsilon^{-2} n^2 )$ time. Therefore, in the natural setting of constant $varepsilon$, we close the gap between the $ ilde O(n^{2.5})$ randomized algorithm and the $ ilde 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(nvarepsilon^{-1} log U)log (n varepsilon) log^2 U)$ time. The previous best deterministic algorithm [APPROX 2016] runs in $O(n^3varepsilon^{-1}log(n varepsilon^{-1} log U) log^2 U)$ time.