In the Colored Bin Packing problem a set of items with varying weights and colors must be packed into bins of uniform weight limit such that no two items of the same color may be packed adjacently within a bin. We solve this problem for the case where there are two or more colors when the items have zero weight and when the items have unit weight. Our algorithms are optimal and run in linear time. Since our algorithms apply for two or more colors, they demonstrate that the problem does not get harder as the number of colors increases. We also provide closed-form expressions for the optimal number of bins.
In this paper, we investigate Colored Bin Packing with constraints - i.e. two items with the same color cannot be packed adjacently to each other in a bin. This 2-color variant was first introduced by , who studied both the offline and online versions of the problem @cite_2 . For the offline version the authors presented a 2.5-approximation algorithm. For the online version, they proved that classical algorithms (First, Best, Worst, Next, Harmonic) are not constant competitive, and hence do not perform well. They further proved a universal lower bound of approximately 1.7213. This exceeds classical Bin Packing's upper bound of 1.5889, proving that Colored Bin Packing with alternation is harder @cite_1 . The authors' main result was a 3-competitive online algorithm, . The main concept of the algorithm is quite elegant. Using pseudo", i.e. dummy, items of different color and zero weight, their algorithm creates an acceptable sequence of colors that are later substituted with actually released items. If any bin overflows, Pseudo redistributes the extra items using Any Fit into available bins, and creates new bins if necessary.
@cite_1 @cite_2
2078659331 2177689085
A new framework for analyzing online bin packing algorithms is presented. This framework presents a unified way of explaining the performance of algorithms based on the Harmonic approach. Within this framework, it is shown that a new algorithm, Harmonic++, has asymptotic performance ratio at most 1.58889. It is also shown that the analysis of Harmonic+1 presented in Richey [1991] is incorrect; this is a fundamental logical flaw, not an error in calculation or an omitted case. The asymptotic performance ratio of Harmonic+1 is at least 1.59217. Thus, Harmonic++ provides the best upper bound for the online bin packing problem to date. We introduce the following version of bin packing. The items are of two types (black and white), and in each bin the item types must alternate. We mostly investigate the online scenario. We study the competitiveness of some classical algorithms (First Best Worst Next Fit, Harmonic) — they do not perform very well — and for all online algorithms we also prove the universal lower bound (1+ 1 2 .7213 ) which significantly exceeds the known upper bound 1.58889 on classical online bin packing. We also design an online algorithm which is 3-competitive in the absolute sense. A 2.5-approximation algorithm and an APTAS is also given for the offline version.