An APTAS for Bin Packing with Clique-graph Conflicts
share
We study the following variant of the classic bin packing problem. The input is a set of items I = { 1, … , N } with corresponding sizes s_1,...,s_N ∈ (0,1], partitioned into n groups G_1,...,G_n. The goal is to pack the items in a minimum number of unit size bins, such that no two items of the same group are packed in the same bin. This group bin packing (GBP) problem, also known as bin packing with clique-graph conflicts, has natural applications in storing file replicas, security in cloud computing and signal distribution. In this paper, we present an asymptotic polynomial time approximation scheme (APTAS) for group bin packing, thus improving the best known ratio of 2 [Adany et al., 2016]. In particular, for any instance I and a fixed ε∈ (0,1), our scheme packs the items in at most (1+ε)OPT(I)+1 bins, where OPT(I) is the minimum number of bins required for packing the instance.
READ FULL TEXT