Colorful bin packing

DOI10.1007/978-3-319-08404-6_15MaRDI QIDQ3188892zbMATH OpenOpenAlexFDO

Publication date 2 September 2014

Published in Algorithm Theory – SWAT 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.3990

Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27)

Abstract: 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.

Recommendations

Cited in

(20)

This page was built for publication: Colorful bin packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188892)