论文标题
通过有界单调最小卷积的更快的背包算法
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution
论文作者
论文摘要
我们为0-1 knapsack和无界背包提供了新的精确和近似算法： * 0-1-knapsack的精确算法：0-1-knapsack已知算法$ \ widetilde {o}（n + \ min \ {n opt，n w，n w，n w，opt^2，w^2 \}）$，其中$ n $是项目的数量，$ w $是权重预算，$ opt $ $ opt $ insal insal insal insal insal insal。我们提出了一种在时间上运行的算法$ \ widetilde {o}（n +（w + opt）^{1.5}）$。如果$ n，w，opt $大致相等，则可以改善运行时间。 *无界背包的确切算法：无限的背包已知已知的算法$ \ widetilde {o}（n + \ min \ {n \ cdot p _ {\ max}，n \ max}，n \ cdot w _ {\ max}，p _ {\ max}，p _ { [Axiotis，Tzamos '19，Jansen，Rohwedder '19，Chan，He '20]，其中$ n $是项目的数量，$ w _ {\ max} $是任何物品中最大的重量，而$ p _ {\ max} $是任何物品的最大利润。我们提出了一种在时间上运行的算法$ \ widetilde {o}（n +（p _ {\ max} + w _ {\ max}）^{1.5}）$，给出了与0-1-knapsack相似的改进。 *与资源增强的无限背包近似：无限的背包具有一个已知的fptas，其运行时间$ \ widetilde {o}（\ min \ {n/\ varepsilon，n + 1/\ varepsilon^2 \} 2 \} 2 \}）$ [jansen，kraft '18]。我们研究弱近似算法，该算法近似最佳利润，但可以超过重量约束。我们介绍了在此设置中无界背包的第一个近似方案，以实现运行时间$ \ widetilde {o}（n + 1/\ varepsilon^{1.5}）$。 我们的算法可以看作是带有有界条目的单调序列上的最小横向卷积的减少。可以在时间$ o（n^{1.5}）$ [Chi，Duan，Xie，Zhang '22]的时间内解决这些结构化实例（与猜想的$ n^{2-o（1）} $下限$相反，对于一般情况而言）。
We present new exact and approximation algorithms for 0-1-Knapsack and Unbounded Knapsack: * Exact Algorithm for 0-1-Knapsack: 0-1-Knapsack has known algorithms running in time $\widetilde{O}(n + \min\{n OPT, n W, OPT^2, W^2\})$, where $n$ is the number of items, $W$ is the weight budget, and $OPT$ is the optimal profit. We present an algorithm running in time $\widetilde{O}(n + (W + OPT)^{1.5})$. This improves the running time in case $n,W,OPT$ are roughly equal. * Exact Algorithm for Unbounded Knapsack: Unbounded Knapsack has known algorithms running in time $\widetilde{O}(n + \min\{n \cdot p_{\max}, n \cdot w_{\max}, p_{\max}^2, w_{\max}^2\})$ [Axiotis, Tzamos '19, Jansen, Rohwedder '19, Chan, He '20], where $n$ is the number of items, $w_{\max}$ is the largest weight of any item, and $p_{\max}$ is the largest profit of any item. We present an algorithm running in time $\widetilde{O}(n + (p_{\max} + w_{\max})^{1.5})$, giving a similar improvement as for 0-1-Knapsack. * Approximating Unbounded Knapsack with Resource Augmentation: Unbounded Knapsack has a known FPTAS with running time $\widetilde{O}(\min\{n/\varepsilon, n + 1/\varepsilon^2\})$ [Jansen, Kraft '18]. We study weak approximation algorithms, which approximate the optimal profit but are allowed to overshoot the weight constraint. We present the first approximation scheme for Unbounded Knapsack in this setting, achieving running time $\widetilde{O}(n + 1/\varepsilon^{1.5})$. Our algorithms can be seen as reductions to Min-Plus-Convolution on monotone sequences with bounded entries. These structured instances of Min-Plus-Convolution can be solved in time $O(n^{1.5})$ [Chi,Duan,Xie,Zhang '22] (in contrast to the conjectured $n^{2-o(1)}$ lower bound for the general case).
