We revisit the classic 0-1-Knapsack problem, in which we are given $n$ items with their weights and profits as well as a weight budget $W$, and the goal is to find a subset of items of total weight at most $W$ that maximizes the total profit. We study pseudopolynomial-time algorithms parameterized by the largest profit of any item $p_{\max}$, and the largest weight of any item $w_{\max}$. Our main result are algorithms for 0-1-Knapsack running in time $\tilde{O}(n\,w_\max\,p_\max^{2/3})$ and $\tilde{O}(n\,p_\max\,w_\max^{2/3})$, improving upon an algorithm in time $O(n\,p_\max\,w_\max)$ by Pisinger [J. Algorithms '99]. In the regime $p_\max \approx w_\max \approx n$ (and $W \approx \mathrm{OPT} \approx n^2$) our algorithms are the first to break the cubic barrier $n^3$. To obtain our result, we give an efficient algorithm to compute the min-plus convolution of near-convex functions. More precisely, we say that a function $f \colon [n] \mapsto \mathbf{Z}$ is $\Delta$-near convex with $\Delta \geq 1$, if there is a convex function $\breve{f}$ such that $\breve{f}(i) \leq f(i) \leq \breve{f}(i) + \Delta$ for every $i$. We design an algorithm computing the min-plus convolution of two $\Delta$-near convex functions in time $\tilde{O}(n\Delta)$. This tool can replace the usage of the prediction technique of Bateni, Hajiaghayi, Seddighin and Stein [STOC '18] in all applications we are aware of, and we believe it has wider applicability.
翻译:本文重新审视经典的 0-1 背包问题,即已知 $n$ 个物品的重量和价值,以及一个重量上限 $W$,求从这些物品中选出若干个物品,并使它们的总重量不超过 $W$ 的前提下,价值最大的物品集合。我们研究基于物品中任意一个物品的价值 $p_{max}$ 和最大重量 $w_{max}$ 的伪多项式时间算法。本文的主要结果是 0-1 背包问题的算法运行时间为 $\tilde{O}(n w_{max} p_{max}^{2/3})$ 和 $\tilde{O}(n p_{max} w_{max}^{2/3})$,相较于 Pisinger 在 1999 年提出的运行时间为 $O(n p_{max} w_{max})$ 的算法有所提高。在 $p_{max} \approx w_{max} \approx n$(且 $W\approx \mathrm{OPT} \approx n^2$)的情况下,本文算法是首个突破 $n^3$ 立方时间复杂度的算法。为了得到这个结果,我们提出了一种计算近凸函数 min-plus 卷积的高效算法。更准确地说,我们称一个函数 $f \colon [n] \mapsto \mathbf{Z}$ 是 $\Delta$-近凸函数,其中 $\Delta \geq 1$,如果存在一个凸函数 $\check{f}$,使得 $\check{f}(i) \leq f(i) \leq \check{f}(i) + \Delta$ 对于所有 $i$ 成立。我们设计了一种算法,可以在时间复杂度 $\tilde{O}(n\Delta)$ 内计算两个 $\Delta$-近凸函数的 min-plus 卷积。这个工具可替代 Bateni, Hajiaghayi, Seddighin 和 Stein 在 2018 年提出的预测技巧,在我们所知的所有应用中都可使用,并且我们认为它有更广泛的适用性。