论文标题
使用彩虹匹配来解决几个小项目的包装问题
Solving Packing Problems with Few Small Items Using Rainbow Matchings
论文作者
论文摘要
组合优化的一个重要领域是研究包装和覆盖问题，例如垃圾箱，多种背包和垃圾箱覆盖物。这些问题已经从近似算法的角度进行了广泛的研究，但是几乎没有研究它们的参数复杂性。对于不包含“小”项目的问题实例，经典匹配算法在多项式时间内产生最佳解决方案。在本文中，我们通过与琐碎的距离接触他们，以小物品的数字$ k $来衡量问题的复杂性。 我们的主要结果是固定参数算法，用于bin包装的矢量版本，多种背包和bin覆盖$ k $的参数。这些算法是随机分配的，并在时间上运行$ 4^{k} \ cdot k！ \ cdot n^{o（1）} $。为了实现这一目标，我们引入了一个有色匹配的问题，我们将所有这些包装问题减少了。有色匹配的问题本身是自然的，我们希望它对其他应用程序有用。我们还提出了一个确定性的固定参数，用于使用运行时间$（k！）^{2} \ cdot k \ cdot 2^{k} \ cdot n \ cdot \ cdot \ log（n）$的确定性固定参数。
An important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been studied extensively from the viewpoint of approximation algorithms, but their parameterized complexity has only been investigated barely. For problem instances containing no "small" items, classical matching algorithms yield optimal solutions in polynomial time. In this paper we approach them by their distance from triviality, measuring the problem complexity by the number $k$ of small items. Our main results are fixed-parameter algorithms for vector versions of Bin Packing, Multiple Knapsack, and Bin Covering parameterized by $k$. The algorithms are randomized with one-sided error and run in time $4^{k} \cdot k! \cdot n^{O(1)}$. To achieve this, we introduce a colored matching problem to which we reduce all these packing problems. The colored matching problem is natural in itself and we expect it to be useful for other applications. We also present a deterministic fixed-parameter for Bin Packing with run time $(k!)^{2}\cdot k \cdot 2^{k}\cdot n\cdot \log(n)$.
