@techreport{TR-IC-10-18,
   number = {IC-10-18},
   author = {Andrew Twigg and Eduardo C. Xavier},
   title = {{Locality-preserving allocations Problems and coloured Bin
                   Packing}},
   month = {May},
   year = {2010},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 18 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       We  study  the following problem, introduced by Chung et al. 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 $\alpha$ times
       optimal),  and  that the items of each colour span few bins (at
       most $\beta$ times optimal). We call such allocations $(\alpha,
       \beta)$-approximate.  We  prove  that  for  $\epsilon>0$, if we
       desire   small  $\alpha$,  no  scheme  can  beat  $(1+\epsilon, 
       \Omega(1/\epsilon))$-approximate  allocations  and similarly as
       we   desire   small   $\beta$,   no  scheme  can  beat  $(1.69, 
       1+\epsilon)$-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+\epsilon, 1.7)$-approximate allocations.
  }
}