Knapsack and Subset Sum with Small Items
Knapsack and Subset Sum with Small Items
复制标题
背包和小件物品的子集总和
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Karol Wkegrzycki
中科院分区：
文献类型：
--
作者：
Adam Polak;Lars Rohwedder;Karol Wkegrzycki
背包问题和子集和问题是组合优化中的基本NP难问题。最近，人们越来越有兴趣了解这些问题关于各种参数的最佳可能的伪多项式运行时间。本文主要研究最大项数$S$和最大项值$v$。对于背包问题，我们给出了时间为$O(n+S^3)$和$O(n+v^3)$的算法；对于子集和问题，给出了时间为$ilde{O}(n+S^{5/3})$的算法。我们的算法适用于更一般的具有多重性的问题变体，其中每个输入项都有一个(二进制编码的)多重性，它简洁地描述了该项在实例中出现的次数。在这些变体中，$n$表示不同项目的数量(可能要少得多)。我们的结果是结合和优化了几个不同的研究路线，特别是由于Eisenbrand和Weismantel(Talg 2019)的整数规划的逼近性论点，Kellerer和Pferschy(J.comb)的快速结构化$(min，+)$-卷积。奥蒂姆。2004)，以及源于Galil和Margalit的加法组合学方法(SICOMP 1991)。
Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In this paper we focus on the maximum item size $s$ and the maximum item value $v$. We give algorithms that run in time $O(n + s^3)$ and $O(n + v^3)$ for the Knapsack problem, and in time $ ilde{O}(n + s^{5/3})$ for the Subset Sum problem. Our algorithms work for the more general problem variants with multiplicities, where each input item comes with a (binary encoded) multiplicity, which succinctly describes how many times the item appears in the instance. In these variants $n$ denotes the (possibly much smaller) number of distinct items. Our results follow from combining and optimizing several diverse lines of research, notably proximity arguments for integer programming due to Eisenbrand and Weismantel (TALG 2019), fast structured $(min,+)$-convolution by Kellerer and Pferschy (J. Comb. Optim. 2004), and additive combinatorics methods originating from Galil and Margalit (SICOMP 1991).
子集和的近线性伪多项式时间算法
DOI：
10.1137/1.9781611974782.69
发表时间：
2017
期刊：
影响因子：
--
作者：
K. Bringmann
通讯作者：
K. Bringmann