We study the following problem, introduced by in 2006. We are given, online or offline, a set of coloured items of different sizes, and wish to pack them into bins of equal size so that we use few bins in total (at most α times optimal), and that the items of each colour span few bins (at most β times optimal). We call such allocations ( α , β ) -approximate. As usual in bin packing problems, we allow additive constants and consider ( α , β ) as the asymptotic performance ratios. We prove that for e 0 , if we desire small α, no scheme can beat ( 1 + e , ? ( 1 e ) ) -approximate allocations and similarly as we desire small β, no scheme can beat ( 1.69103 , 1 + e ) -approximate allocations. We give offline schemes that come very close to achieving these lower bounds. For the online case, we prove that no scheme can even achieve ( O ( 1 ) , O ( 1 ) ) -approximate allocations. However, a small restriction on item sizes permits a simple online scheme that computes ( 2 + e , 1.7 ) -approximate allocations.
The class-constrained bin packing problem', studied by @cite_16 , @cite_2 , @cite_10 and @cite_6 is a coloured bin packing problem. The aim is to minimize the number of bins used, subject to the constraint that each bin contains items from at most @math different colours (and subject to its capacity constraints). This problem has applications in developing algorithms for data placement on parallel disk arrays. Again, optimal solutions to this problem may be arbitrarily far from good if we wish to minimize colour stretch.
@cite_16 @cite_10 @cite_6 @cite_2
166203068 1781979225 2032887760 2160306680
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. In the Colored Bin Packing problem a sequence of items of sizes up to (1 ) arrives to be packed into bins of unit capacity. Each item has one of (c 2 ) colors and an additional constraint is that we cannot pack two items of the same color next to each other in the same bin. The objective is to minimize the number of bins. In this paper we present approximation results for the class constrained bin packing problem that has applications to Video-on-Demand Systems. In this problem we are given bins of size B with C compartments, and n items of Q different classes, each item i@? 1,...,n with class c"i and size s"i. The problem is to pack the items into bins, where each bin contains at most C different classes and has total items size at most B. We present several approximation algorithms for offline and online versions of the problem. In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1 , and n items of Q different classes, each item e with class c e and size s e . The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size d . In a shelf bin packing problem, we have to obtain a shelf packing such that the total size of items and shelf divisors in any bin is at most 1. A dual approximation scheme must obtain a shelf packing of all items into N bins, such that, the total size of all items and shelf divisors packed in any bin is at most 1 + e for a given e > 0 and N is the number of bins used in an optimum shelf bin packing problem. Shelf divisors are used to avoid contact between items of different classes and can hold a set of items until a maximum given weight. We also present a dual approximation scheme for the class constrained bin packing problem. In this problem, there is no use of shelf divisors, but each bin uses at most C different classes.