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.
There are some other variants of bin packing problems with colours, for example the so called Colored Bin Packing that has the restriction that items of a same colour cannot be packed next to each other on a same bin. Approximation algorithms for the online version of the problem were presented by B "o @cite_14 and Dosa and Epstein @cite_9 . A generalization where the objective is to pack a graph @math into another graph @math where nodes into @math have capacities and nodes in @math corresponds to items of given size, was studied by Bujt 'a in @cite_0
@cite_0 @cite_9 @cite_14
166203068 1781979225
In the three-dimensional (3D) strip packing problem, we are given a set of 3D rectangular items and a 3D box @math . The goal is to pack all the items in @math such that the height of the packing is minimized. We consider the most basic version of the problem, where the items must be packed with their edges parallel to the edges of @math and cannot be rotated. Building upon Caprara's work for the two-dimensional (2D) bin packing problem, we obtain an algorithm that, given any @math , achieves an approximation of @math , where @math is the well-known number that occurs naturally in the context of bin packing. Our key idea is to establish a connection between bin packing solutions for an arbitrary instance @math and the strip packing solutions for the corresponding instance obtained from @math by applying the harmonic transformation to certain dimensions. Based on this connection, we also give a simple alternate proof of the @math approximation for 2D ... 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. The bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes a 1 ,…, a n in (0,1]. Using uniform sampling, which selects a random element from the input list each time, we develop a randomized @math time (1+e )-approximation scheme for the bin packing problem. We show that every randomized algorithm with uniform random sampling needs @math time to give an (1+e )-approximation. For each function s (n ): N →N , define ∑(s (n )) to be the set of all bin packing problems with the sum of item sizes equal to s (n ). We show that ∑(n b ) is NP-hard for every b ∈(0,1]. This implies a dense sublinear time hierarchy of approximation schemes for a class of NP-hard problems, which are derived from the bin packing problem. We also show a randomized streaming approximation scheme for the bin packing problem such that it needs only constant updating time and constant space, and outputs an (1+e )-approximation in @math time. Let S (δ )-bin packing be the class of bin packing problems with each input item of size at least δ . This research also gives a natural example of NP-hard problem (S (δ )-bin packing) that has a constant time approximation scheme, and a constant time and space sliding window streaming approximation scheme, where δ is a positive constant. 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.