2020/11/09 by Ilan Doron-Arad, Doron-Arad, Ilan, Ariel Kulik +3
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Optimization and Packing Problems #Optimization and Search Problems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.2011.04273
arxiv created 2021/06/05 · arxiv updated 2021/06/08
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 ∈ (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.