  We study a variant of online bin packing, called colorful bin packing. In
this problem, items that are presented one by one are to be packed into bins of
size 1. Each item i has a size s_i \in [0,1] and a color c_i \in C, where C is
a set of colors (that is not necessarily known in advance). The total size of
items packed into a bin cannot exceed its size, thus an item i can always be
packed into a new bin, but an item cannot be packed into a non-empty bin if the
previous item packed into that bin has the same color, or if the occupied space
in it is larger than 1-s_i. This problem generalizes standard online bin
packing and online black and white bin packing (where |C|=2). We prove that
colorful bin packing is harder than black and white bin packing in the sense
that an online algorithm for zero size items that packs the input into the
smallest possible number of bins cannot exist for C \geq 3, while it is known
that such an algorithm exists for |C|=2. We show that natural generalizations
of classic algorithms for bin packing fail to work for the case |C| \geq 3 and
moreover, algorithms that perform well for black and white bin packing do not
perform well either, already for the case |C|=3. Our main results are a new
algorithm for colorful bin packing that we design and analyze, whose absolute
competitive ratio is 4, and a new lower bound of 2 on the asymptotic
competitive ratio of any algorithm, that is valid even for black and white bin
packing.
