text: 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.
  @cite_16: We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of M multimedia objects (data objects) that need to be assigned to a storage system consisting of N disks d1,d2…,dN. We are also given sets U1,U2,…,UM such that Ui is the set of clients seeking the ith data object. Each disk dj is characterized by two parameters, namely, its storage capacity Cj which indicates the maximum number of data objects that may be assigned to it, and a load capacity Lj which indicates the maximum number of clients that it can serve. The goal is to find a placement of data objects to disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system. We study this data placement problem for two natural classes of storage systems, namely, homogeneous and uniform ratio. We show that an algorithm developed by Shachnai and Tamir [2000a] for data placement achieves the best possible absolute bound regarding the number of clients that can always be satisfied. We also show how to implement the algorithm so that it has a running time of O((N + M) log(N + M)). In addition, we design a polynomial-time approximation scheme, solving an open problem posed in the same paper.
  @cite_10: 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.
  @cite_6: 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.
  @cite_2: We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of M multimedia objects (data items) that need to be assigned to a storage system consisting of N disks d1, d2,...,dN. We are also given sets U1, U2,...,UM such that Ui is the set of clients seeking the ith data item. Data item i has size si. Each disk dj is characterized by two parameters, namely, its storage capacity Cj which indicates the maximum total size of data items that may be assigned to it, and a load capacity Lj which indicates the maximum number of clients that it can serve. The goal is to find a placement of data items to disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system.We study this data placement problem for homogeneous storage systems where all the disks are identical. We assume that all disks have a storage capacity of k and a load capacity of L. Previous work on this problem has assumed that all data items have unit size, in other words si = 1 for all i. Even for this case, the problem is NP-hard. For the case where si ∈ 1,..., Δ for some constant Δ, we develop a polynomial time approximation scheme (PTAS). This result is obtained by developing two algorithms, one that works for constant k and one that works for arbiuary k. The algorithm for arbitrary k guarantees that a solution where at least ((k-Δ) (k + Δ))(1 - 1 (1 + √k (2Δ))2)- fraction of all clients are assigned to a disk (under certain assumptions). In addition we develop an algorithm for which we can prove tight bounds when si ∈ 1,2 . In fact, we can show that a (1 - 1 (1 + √⌊k 2⌋)2)-fraction of all clients can be assigned (under certain natural assumptions), regardless of the input distribution.
summary: 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.