论文标题
用于包装包装的APTA，用clique-graph冲突
An APTAS for Bin Packing with Clique-graph Conflicts
论文作者
论文摘要
我们研究了经典{\ em bin包装}问题的以下变体。给定一组各种大小的项目，分别为组，以最少数量的相同（单位大小）垃圾箱的数量找到这些项目的包装，因此同一组的两个项目没有分配给同一垃圾箱。这个问题被称为{\ em bin带有clique-graph冲突}，在存储文件副本，云计算中的安全性和信号分布中具有自然应用。 我们的主要结果是解决问题的{\ em渐近多项式时间近似方案（APTAS）}，以$ 2 $的最佳已知比率提高。尤其是％，对于任何实例，$ i $和固定的$ \ eps \ in（0,1）$，这些物品最多包含在$（1+ \ eps）opt（i） +1 $ bins中，其中$ opt（i）$是包装实例所需的最小垃圾箱。作为关键工具，我们应用了一种小说{\ em Shift \＆Swap}技术，该技术将经典的线性转移技术推广到允许项目之间冲突的场景中。仅使用少量额外垃圾箱包装{\ em小}项目的主要挑战是通过复杂的枚举组合和一种利用{\ em linear program}的圆形解决方案的贪婪的方法来解决的。
We study the following variant of the classic {\em bin packing} problem. Given a set of items of various sizes, partitioned into groups, find a packing of the items in a minimum number of identical (unit-size) bins, such that no two items of the same group are assigned to the same bin. This problem, known as {\em bin packing with clique-graph conflicts}, has natural applications in storing file replicas, security in cloud computing and signal distribution. Our main result is an {\em asymptotic polynomial time approximation scheme (APTAS)} for the problem, improving upon the best known ratio of $2$. %In particular, for any instance $I$ and a fixed $\eps \in (0,1)$, the items are packed in at most $(1+\eps)OPT(I) +1$ bins, where $OPT(I)$ is the minimum number of bins required for packing the instance. As a key tool, we apply a novel {\em Shift \& Swap} technique which generalizes the classic linear shifting technique to scenarios allowing conflicts between items. The major challenge of packing {\em small} items using only a small number of extra bins is tackled through an intricate combination of enumeration and a greedy-based approach that utilizes the rounded solution of a {\em linear program}.
