We study the following variant of the classic bin packing problem. The input is {\em   a set of items I = \{ 1 , %DIFDELCMD < \dots %%% , N \} with corresponding sizess_1, ...,s_N \in (0 , 1 , partitioned into n groupsG_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{\em 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{\em asymptotic polynomial time approximation scheme (APTAS) for group bin packing, thus improving the best known ratio of 2 Adany et al., 2016%DIFDELCMD < ]%%% . In particular, for any instance I and a fixed \varepsilon \eps \in (0,1), our scheme packs the items in at most (1+ \varepsilon \eps )OPT(I) +1 bins, where OPT(I) is the minimum number of bins required for packing the instance {\em  {\em  {\em  .
We study the following variant of the classic {\em bin packing problem. Given a set of items of various sizes , %DIFDELCMD < \dots %%% 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 %DIFDELCMD < ]%%% 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 .
D
bin packing problem. The input is
A
bin packing
A
problem. Given
R
I = \{ 1
of various sizes
R
, N \} with corresponding sizess_1, ...,s_N \in (0
partitioned into groups
D
1
R
, partitioned into n groupsG_1, ...,G_n. The goal is to pack
find a packing of
R
unit size
identical (unit-size)
R
packed in
assigned to
R
group bin packing (GBP) problem, also known as
problem, known as
R
In this paper, we present an
Our main result is an
R
for group bin packing, thus improving
for the problem, improving upon
D
2
D
Adany et al., 2016
R
.
2. \%
D
\varepsilon
R
our scheme packs the items
the items are packed
D
\varepsilon
A
. As a key tool, we apply a novel
A
Shift \& Swap
A
technique which generalizes the classic linear shifting technique to scenarios allowing conflicts between items. The major challenge of packing
A
small
A
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
A
linear program