The Taub Faculty of Computer Science Events and Talks

We study the following variant of the classic 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 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 asymptotic polynomial time approximation scheme (APTAS) for the problem, improving upon the best known ratio of 2. In particular, given an instance I for the problem and a parameter epsilon > 0, our scheme packs the instance in at most (1+epsilon)OPT(I)+c bins, where OPT(I) is the minimum number of bins required for packing the instance, and c > 0 is some constant. As a key tool, we apply a novel Shift & Swap technique which generalizes the classic linear shifting technique to scenarios allowing conflicts between the items. The major challenge of packing 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 linear program.