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.
explored a zero-weight version of the 2-color variant of this problem @cite_0 . They show that in this case, the optimal number of bins equals the color - the absolute difference between the number of items of the two colors. The paper's main result is an optimal algorithm, named Balancing Any Fit, which operates on the simple principle that an item should be packed in an available bin containing the most oppositely-colored items. This is made easier since weight is not an issue.
@cite_0
166203068 2177689085 2050319410 1975625792
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 ∈ [0,1] and a color (c_i 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 | 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 | 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. 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. We study the following variant of the bin packing problem. We are given a set of items, where each item has a (non-negative) size and a color. We are also given an integer parameter k, and the goal is to partition the items into a minimum number of subsets such that for each subset S in the solution, the total size of the items in S is at most 1 (as in the classical bin packing problem) and the total number of colors of the items in S is at most k (which distinguishes our problem from the classical version). We follow earlier work on this problem and study the problem in both offline and online scenarios. Bin covering takes as input a list of items with sizes in (0, 1) and places them into bins of unit demand so as to maximize the number of bins whose demand is satisfied. This is in a sense a dual problem to the classical one-dimensional bin packing problem, but has for many years lagged behind the latter in terms of the quality of the best approximation algorithms. We design algorithms for this problem that close the gap, both in terms of worst- and average-case results. We present (1) the first asymptotic approximation scheme for the offline version, (2) algorithms that have bounded worst-case behavior for instances with discrete item sizes and expected behavior that is asymptotically optimal for all discrete “perfect-packing distributions” (ones for which optimal packings have sublinear expected waste), and (3) a learning algorithm that has asymptotically optimal expected behavior for all discrete distributions. The algorithms of (2) and (3) are based on the recently-developed online Sum-of-Squares algorithm for bin packing. We also present experimental analysis comparing the algorithms of (2) and suggesting that one of them, the Sum-of-Squares-with-Threshold algorithm, performs quite well even for discrete distributions that do not have the perfect-packing property.