Black And White Bin Packing Revisited
Document Type
Conference Proceeding
Publication Date
12-9-2015
Publication Title
Combinatorial Optimization and Applications
Volume
9486
First page number:
45
Last page number:
59
Abstract
The black and white bin packing problem is a variant of the classical bin packing problem, where in addition to a size, each item also has a color (black or white), and in each bin the colors of items must alternate. The problem has been studied extensively, but the best competitive online algorithm has competitiveness of 3. The competitiveness of 3 can be forced even when the sizes of items are ‘halved’, i.e. the sizes are restricted to be in (0, 1 / 2]. We give the first ‘better than 3’ competitive algorithm for the problem for the case that item sizes are in the range (0, 1 / 2]; our algorithm has competitiveness 8383.
Language
eng
Repository Citation
Han, X.,
Chen, J.,
Bein, W.,
Ting, H.
(2015).
Black And White Bin Packing Revisited.
Combinatorial Optimization and Applications, 9486
45-59.
http://dx.doi.org/10.1007/978-3-319-26626-8_4