@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.
}
}