A Two-Pass Algorithm for Unordered Colored Bin Packing

Abstract

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 consider a version of the problem where there is no ordering among the items. We present exact, linear-time algorithms for this problem for the cases where there are two or more colors when the items have zero weight and when the items have unit weight. Our algorithms require only two passes over the input items. We also nd closed-form expressions for the optimal number of bins.

Keywords

• algorithms
• combinatorial optimization
• bin packing
• colors
• class constraints

Introduction

subsets of items of the same color while maintaining a count of each subset and the most frequent color. The second pass performs the packing. We note that the rst pass is a pre-processing step and does not involve any packing. Therefore if the input was instead given as (1) k subsets S1; S2; : : : ; Sk where k is the number of colors, and S1 contains the items of the most frequent color and Si for i > 1 contains the items of color i, and (2) jS1j (i.e. the number of items of the most frequent color) and jS2j + jS3j + : : : + jSkj (i.e. the number of items of other colors), our algorithm would require just one pass to pack the items. Another advantage of our algorithms is that, similar to many classical Bin Packing algorithms (Best-Fit, First-Fit, Next-Fit), they are simple; however their optimality is not obvious.

This Colored Bin Packing problem has many practical applications as described in [ 2 ]. For example, television and radio stations often schedule a set of programs on different channels. Each program may fall into a genre such as comedy, documentary, and sports, on TV, or various musical genres on radio. To maintain a diverse schedule of programs, the station would like to avoid broadcasting two programs of the same genre one after the other. This problem can be modeled as Colored Bin Packing where the items correspond to programs, colors to genres, and bins to channels.

Another application involves generating diverse content to be displayed on websites. Many websites prefer displays that alternate between different types of information and advertisements and the Colored Bin Packing problem can be used to generate such a display. The items correspond to the contents to display, the colors to the type of content, and the bins to the size of the display.

The remainder of this paper is organized as follows. In Section 1.1 we discuss several previous results related to the Colored Bin Packing problem. In Sections 2 and 3 we present our results for zero-weight and unit-weight items, respectively. In Section 4 we provide closed-form expressions for the optimal number of bins. 1.1

Related Work

Classic Bin Packing is a well known problem, with many applications throughout various elds. Bin Packing with color constraints is relatively recent, arising with the increasing complexity of contemporary industrial processes. The use of color gives classic Bin Packing added exibility in modeling real-world problems. For example, Oh and Son used color, speci cally, the requirement that two items with the same color cannot be packed in the same bin, to efficiently assign tasks in real time within a multiprocessor system [ 10 ]. Their result was a modi ed First Fit algorithm that is 1.7-competitive in the worst case, and 1.1 in the average case. Dawande et al. investigated a version of Colored Bin Packing where each bin has a maximum color capacity [ 3 ] i.e. a limit on the number of items of a particular color. Such a problem models the slab design problem in the production planning process of a steel plant. The authors present two 3-approximation algorithms, classical First-Fit-Decreasing, and a modi ed First Fit. Epstein et al. also studied Colored Bin with color capacities. They prove upper and lower bounds for several variants of this problem in both the offline and online settings. Xavier and Miyazawa use Bin Packing with Colors (they refer to the colors as classes ) to model Video-on-Demand applications [ 12 ]. Speci cally, there is a server of multiple disks that each have limited storage capacity and can hold video les of varying sizes and genres (i.e. classes). The application is given an expected number of requests for movies based on movie/genre popularity. The goal is to construct a server that maximizes the number of satis ed requests. A more generalized version of constrained bin packing where the constraints among items are de ned in a con ict graph have been studied by Jansen [ 6 ] and Muritiba et al. [ 9 ].

Balogh et al. introduced the Black and White Bin Packing problem with alternation constraints, where two items with the same color cannot be packed adjacently to each other in a bin [ 1 ]. They studied both the offline and online versions of the problem. 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 Black and White Bin Packing with alternation is harder [ 11 ]. The authors' main result was a 3-competitive online algorithm, Pseudo. 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 over ows, Pseudo redistributes the extra items using Any Fit into available bins, and creates new bins if necessary.

Bohm et al. explored the online Colored Bin Packing with alternation constraints where there two or more colors [ 2 ]. They study this problem for the restricted offline setting, i.e. where the items are presented in a particular order and must be packed in this order, which is a harder version of the problem we address. For zero-weight items, they present a recursive algorithm whose straightforward implementation runs in O(n2) time, where n is the number of items. Although our algorithms solve an easier problem, they do so with at most two passes over the input. Bohm et al. also show that the optimal number of bins equals the color discrepancy - the absolute difference between the number of items of the two colors. The paper's main result is an optimal online algorithm for the zero-weight case, named Balancing Any Fit, that 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.

Dosa and Epstein [ 4 ] extend the results from [ 1 ]. They prove that online Colored Bin Packing with alternation for 3 or more colors is harder than the 2-color version. Furthermore, the authors show that 2-color algorithms do not apply to 3 or more color problems. They also proved that no optimal algorithm exists for online Colored Bin Packing when there are more than two colors even when the items have zero-weight. Lastly, they present a 4-competitive algorithm for the problem. This is a modi ed version of the earlier Pseudo, appropriately named Balanced-Pseudo. Instead of randomly assigning items to available bins, Balanced-Pseudo assigns an item to the bin whose top color is the most frequent.

In this paper we consider the offline Colored Bin Packing problem where there is no ordering among the items. We present exact linear time algorithms that solve this problem for two or more colors when the items have zero-weight and when the items have unit-weight. This problem is related to the problem of nding alternating Euler tours in edge-colored graphs [ 7 ]. However, our work is different in that (1) it applies to bin packing rather than graphs, (2) the unit-weight case of our problem solves the bounded-length version of the alternating tour problem which has not yet been explicitly solved [ 8 ], and (3) our algorithms solve the problems using at most two passes over the input items. 2

Zero-Weight Colored Bin Packing

For the zero-weight case, the input is a set S of n items, where each item has a color from a set of k colors and weight zero. The Algorithm alternate-zero solves the zeroweight case. We let M axColor denote the most frequent color, i.e. the color with the most number of items, OtherColors denote the set of all other colors and M axCount and OtherCount denote the number of items of M axColor and OtherColors, respectively. In the zero-weight case, the bins do not have a weight limit so the only constraint is that no items of the same color may be packed adjacently in a bin. As in [ 2 ], we nd that the number of bins depends on the discrepancy of the items, i.e. the difference between the number of M axColor and OtherColors items.

Algorithm 1: alternate-zero(S: set of n items) 1: Separate S into S1; S2; : : : ; Sk where S1 contains the items of the most frequent color, M axColor, and Si, for i > 1, contains the set of all items of color i. Also maintain: M axCount: number of items of M axColor, OtherColors: set of all non-M axColor colors, and OtherCount: number of items of OtherColors 2: D = M axCount OtherCount 3: if D 0 then 4: Alternate between OtherColors items until there is one fewer OtherColors item than M axColor item remaining. 5: Start with a M axColor item and alternate between an OtherColors item and a

M axColor item until all items are packed. 6: else 7: Alternate between a M axColor item and an OtherColors item until all

OtherColors items are packed. 8: There will be M axCount OtherCount 1 remaining M axColor items so pack each in its own bin.

9: end if Theorem 1. The Algorithm alternate-zero is optimal for the Zero-Weight Colored Bin Packing Problem.

Proof. We let D = M axCount cases based on D.

OtherCount denote the discrepancy and consider two Case 1: D 0. In this case there are at least as many OtherColors items as there are M axColor items. Therefore, we need only one bin, which is the fewest number

of bins any algorithm will use. If D = 0, we simply alternate between M axColor and OtherColors items. If D < 0, we alternate between items of OtherColors until there is one fewer OtherColors item than M axColor item. At this point, we add one M axColor item to the bin and then alternate between an OtherColors item and a M axColor item until all items are packed. Therefore, we use one bin. Note that to pack the items using exactly one pass, we must rst alternate between OtherColors items before packing any M axColor items. This ensures that we are not left with two or more OtherColors items of the same color.

Also note that when D < 0 (i.e. there are more M axColor items than OtherColors items) there will be enough OtherColors items to alternate between until there is one fewer OtherColors item than M axColor item. Suppose, by contradiction, that this is not the case, so when we can no longer alternate between OtherColors items, the number of OtherColors items is equal to or more than the number of M axColor items. If we can no longer alternate between OtherColors items, it must mean that there is only one color, say C, remaining in the set of OtherColors items left to pack. Let c denote the number of C-colored items left to pack, so c M axCount. Since we must have packed at least one C-colored item and no M axColor items, there must have been at least c + 1 M axCount + 1 C-colored items in the input, which contradicts that M axColor is the most frequent color.

As an example, if we are given 4 White (W), 3 Black (B), 3 Yellow (Y), and 1 Red (R) items, then M axColor is White, M axCount = 4, OtherCount = 7, so D = 3. An optimal packing is: BYBYWBWYWRW. Note that if we started by packing a M axColor item (a tempting choice), we would need to use at least two passes to pack all the items.

Case 2: D > 0. In this case, there are enough M axColor items that each OtherColors item is needed to be packed in between two M axColor items. Therefore, all OtherColors items can be regarded as a single color not equal to M axColor, making this the black/white bin packing problem [ 1 ]. The rst bin will start with a M axColor item, alternate between M axColor and OtherColors items, and end with a M axColor item. Thus, the rst bin will contain all the OtherColors items and OtherCount + 1 M axColor items. There will be M axCount OtherCount 1 M axColor items remaining, each of which must be packed in a separate bin. This gives a total of M axCount OtherCount bins, i.e. the discrepancy. Since the rst bin contains as many M axColor items as possible and none of the additional bins can be combined, this is the optimal packing.

As an example, if we are given 8 W, 2 B, and 2 Y items, then M axCount = 8, OtherCount = 4, so D = 4. An optimal packing is: WBWBWYWYW / W / W / W ( where / denotes a new bin). 3

Unit-Weight Colored Bin Packing

For the unit-weight case, the input is a set S of n items, where each item has a color from a set of k colors and unit weight, and a bin weight limit L. The general idea of Algorithm alternate-unit is as follows. The unit-weight case introduces weight Algorithm 2: alternate-unit(S: set of n items, L: bin weight limit) constraints. However, color constraints, speci cally the discrepancy, may force us to use more bins than the weight constraint alone. Speci cally, if discrepancy does not pose a problem (i.e. is not more than zero), we simply pack the items using a modi ed Alternate-Zero that packs at most L items per bin. If discrepancy is more than zero, the packing depends on whether L is even or odd. In both cases, we start with a M axColor item and alternate between M axColor and OtherColors items. If L is even, it may be optimal to not pack each bin full. Instead we should save OtherColors items for packing in between excess M axColor items. If L is odd, every full bin will contain one more M axColor item than OtherColors item, so our packing may eventually reduce discrepancy to zero. If so, we pack the remaining items as we did in the zeroweight case. Otherwise, we will have bins containing only a single M axColor item. Lemma 1. If D > 0 we can pack at most D bins that contain one more M axColor item than OtherColors item before the discrepancy reduces to zero.

Proof. Packing one such bin reduces the discrepancy to D 1, packing two such bins reduces the discrepancy to D 2, and so on. Therefore, packing D such bins reduces the discrepancy to D D = 0. Therefore, if OtherCount D(L=2 1) for even L or OtherCount D⌊L=2⌋ for odd L, then we can pack D bins that contain one more M axColor item than OtherColors item.

Theorem 2. The Algorithm alternate-unit is optimal for the Unit-Weight Colored Bin Packing Problem.

Proof. As in the zero-weight case, we consider two cases based on the discrepancy: Case 1: D 0. We know from the zero-weight case that Alternate-Zero satis es the color constraint when discrepancy is less than or equal to 0. Therefore, we call a modi ed Alternate-Zero that packs at most L items per bin. Since AlternateZero is optimal, this packing will yield the optimal number of bins.

As an example, if we are given 4 W, 3 B, and 2 Y items, and L = 3, then D = 1 and an optimal packing is BYW / BWB / WYW.

Case 2: D > 0. This is the complex case as now the packing depends on both the weight and the color constraints. We pack bins by starting with a M axColor item and alternating between OtherColors and M axColor items. Since the discrepancy is more than 0, there may be M axColor items remaining. The remainder of the packing depends on whether L is even or odd.

We rst note that when the discrepancy of the remaining items is more than zero, packing as many M axColor items as possible into a bin can never yield a sub-optimal solution. This is because the only reason a M axColor item should be saved for another bin is if it is needed for packing between two OtherColors items. However, this will not happen if there are more M axColor items than OtherColors items. We use this fact to prove the optimality of our algorithms when discrepancy is more than zero.

L is even. Since D > 0 we may end up with single-item bins containing a M axColor item; we refer to these as M-bins. Since D > 0, we pack each bin with as many M axColor

items as possible (i.e. L=2). To reduce the number of M-bins, we save OtherColors items from some bins. The number of OtherColors items we save is essential if we save too few, then we may end up with unnecessary M-bins; if we save too many, then we may end up with OtherColors items of the same color that would need to be packed into separate bins. From Lemma 1, we know that if we save one OtherColors item from each of D bins, then the discrepancy of remaining items will be at most zero. Therefore we pack at most D bins this way and refer to this as the initial packing. We note that there may not be enough OtherColors items to pack D such bins and in this case, the packing will inevitably yield some M-bins. In particular, if OtherCount < D(L=2 1), then we will pack fewer than D such bins, there will be M axColor items remaining, and each of these will be packed in an M-bin. If OtherCount D(L=2 1) then we can pack D such bins and the discrepancy reduces to zero. We then apply the modi ed alternate-zero to pack the remaining items. The bins packed during the initial packing contain as many M axColor items as possible, and we know from Lemma 1, they also contain the optimal number of OtherColors items. From Theorem 1, we know the bins packed using alternate-zero are optimally packed. Therefore the entire packing is optimal.

As an example, if we are given 11 W, 3 B, and 3 Y items, and L = 6, then D = 5 and OtherCount < D(L=2 1). An optimal packing is WBWBW / WBWYW / WYWYW / W / W.

If we are given 11 W, 6 B, and 3 Y items, and L = 6, then D = 2 and OtherCount D(L=2 1). An optimal packing is WBWBW / WBWBW / BWBWYW / YWYW. L is odd.

We begin by packing bins full, starting with a M axColor item, alternating between OtherColors and M axColor items, and topping with a M axColor item. We refer to this as the initial packing. Since L is odd each bin will contain one more M axColor item than OtherColors item. From Lemma 1 we know that D reduces to zero if we are able to pack D bins this way. As in the even case, if OtherCount < D⌊L=2⌋, then we will pack fewer than D such bins, there will be M axColor items remaining, and each of these will be packed in an M-bin. If OtherCount D⌊L=2⌋ then we can pack D such bins and the discrepancy reduces to zero. We then apply the modi ed alternate-zero to pack the remaining items. For the same reason as in the even case, this yields an optimal packing. As an example, if we are given 9 W, 3 B, and 3 Y items, and L = 7, then D = 3, so OtherCount < D⌊L=2⌋. An optimal packing is: WBWBWBW / WBWBWBW / W.

If we are given 7 W, 3 B, and 3 Y items, and L = 7, then D = 1, so OtherCount D⌊L=2⌋. An optimal packing is: WBWBWBW / YWYWYW. 3.1

Two Pass Algorithms

Our algorithms use exactly two passes over the set of input items. Speci cally, in the rst pass, the algorithms separate the items into subsets of items of the same color while maintaining OtherColors, M axCount, OtherCount and determining M axColor. This process requires examining each item exactly once. It then performs the packing using exactly one pass over each input item. 4

Number of Bins

In this section, we provide closed-form expressions for the optimal number of bins. The zero-weight case is straightforward: if the discrepancy D is no more than 0, then one bin is needed; otherwise D bins are needed. For the unit-weight case we consider three sub-cases. 1. D 0: In this case there are enough OtherColors items to pack all the M axColor items such that there will be no M-bins. The number of bins depends on the bin capacity: speci cally there will be ⌈n=L⌉ bins. 2. D > 0 and L is even:

We consider two sub-cases based on OtherCount:

OtherCount < D(L=2 1): In this case, we will run out of OtherColors items before packing D bins. In the initial packing we pack ⌈OtherCount=(L=2 1)⌉ bins that contain L=2 M axColor and L=2 1 OtherColors items, so we pack ⌈OtherCount=(L=2 1)⌉ more M axColor items than OtherColors items during the initial packing. Therefore the initial packing also yields M axCount OtherCount ⌈OtherCount= (L=2 1)⌉ M axColor items that are each packed in an M-bin. Therefore, the total number of bins is ⌈OtherCount=(L=2 1)⌉ + M axCount OtherCount ⌈OtherCount=(L=2 1)⌉ = D.

OtherCount D(L=2 1): In this case, there are enough OtherColors items such that packing D bins with L=2 M axColor items and L=2 1 OtherColors items will eventually reduce D to zero, so there will be no M-bins. Each of these D bins will contain L 1 items so there will be n D(L 1) items remaining after D bins are packed and we will need ⌈ n DL(L 1) ⌉ bins for these items, so the total number of bins is D + ⌈ n D(L 1) ⌉.

L 3. D > 0 and L is odd:

Again we consider two sub-cases based on OtherCount:

OtherCount < D(L=2 1): This case is identical to the even case, so the total number of bins is D. OtherCount D(L=2 1): This case is similar to the even case - the only difference is that each of the D bins will contain L (instead of L 1) items. So the total number of bins is D + ⌈n LDL ⌉.

References

1. J. Balogh , J. Bekesi , G. Dosa, H. Kellerer and Z. Tuza . Black and White Bin Packing. Approximation and Online Algorithms , 10th International Workshop, WAOA, Revised Selected Papers , pp. 131 - 144 , 2012 .

2. M. Bohm , J. Sgall and P. Vesely . Online Colored Bin Packing. Approximation and Online Algorithms , 12th International Workshop, WAOA 2014, Revised Selected Papers, pp. 35 - 45 , 2014 .

3. M. Dawande , J. Kalagnanam and J. Sethuraman . Variable Sized Bin Packing with Color Constraints . IElectronic Notes in Discrete Mathematics, Brazilian Symposium on Graphs, Algorithms and Combinatorics , vol. 7 , pp. 154 - 157 , 2001 .

4. G. Dosa and L. Epstein . Colorful Bin Packing. Algorithm Theory, SWAT , pp. 170 - 181 , 2014 .

5. L. Epstein , C. Imreh , and A. Levin . Class Constrained Bin Packing Revisited. Theoretical Computer Science , vol. 411 , no. 34 , pp. 3073 - 3089 , 2010 .

6. K. Jansen . An Approximation Scheme for Bin Packing with Con icts . Journal of Combinatorial Optimization , vol. 3 , no. 4 , pp. 363 - 377 , 1999 .

7. Y. Manoussakis . Alternating Paths in Edge-Colored Complete Graphs . Discrete Applied Mathematics , vol. 56 , no. 2 , pp. 297 - 309 , 1995 .

8. Y. Manoussakis . Personal communication, April 2016 .

9. A. E. F. Muritiba , M. Iori , E. Malaguti, and P. Toth . Algorithms for the Bin Packing Problem with Con icts . INFORMS Journal on Computing , vol. 22 , no. 3 , pp. 401 - 415 , 2010 .

10. Y. Oh and S. H. Son . On a Constrained Bin Packing Problem . Technical report CS-95-14 . Department of Computer Science, University of Virginia, VA, 1995 .

11. S. Seiden . On the Online Bin Packing Problem . Journal of the ACM (JACM) , pp. 640 - 671 , 2002 .

12. E. Xavier and F. K. Miyazawa . The Class Constrained Bin Packing Problem with Applications to Video-on- Demand . Theoretical Computer Science , vol. 393 , no 1, pp. 240 - 259 , 2008 .