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
2108111372 2032887760 2050319410 2063730794
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. We study the classic Bin Packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio between updates. Formally, each item @math has a @math , and we want to use @math bins and incur a movement cost @math , either in the worst case, or in an amortized sense, for @math as small as possible. We call @math the of the algorithm. This is motivated by cloud storage applications, where fully-dynamic Bin Packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeoffs between number of bins used and number of items repacked, as well as natural extensions of the latter measure. 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. Abstract The bin packing problem is a well-studied problem in combinatorial optimization. In the classical bin packing problem, we are given a list of real numbers in ( 0 , 1 ] and the goal is to place them in a minimum number of bins so that no bin holds numbers summing to more than 1. The problem is extremely important in practice and finds numerous applications in scheduling, routing and resource allocation problems. Theoretically the problem has rich connections with discrepancy theory, iterative methods, entropy rounding and has led to the development of several algorithmic techniques. In this survey we consider approximation and online algorithms for several classical generalizations of bin packing problem such as geometric bin packing, vector bin packing and various other related problems. There is also a vast literature on mathematical models and exact algorithms for bin packing. However, this survey does not address such exact algorithms. In two-dimensional geometric bin packing , we are given a collection of rectangular items to be packed into a minimum number of unit size square bins. This variant has a lot of applications in cutting stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related problems. In d -dimensional vector bin packing , each item is a d -dimensional vector that needs to be packed into unit vector bins. This problem is of great significance in resource constrained scheduling and in recent virtual machine placement in cloud computing. We also consider several other generalizations of bin packing such as geometric knapsack, strip packing and other related problems such as vector scheduling, vector covering etc. We survey algorithms for these problems in offline and online setting, and also mention results for several important special cases. We briefly mention related techniques used in the design and analysis of these algorithms. In the end we conclude with a list of open problems.