  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. As usual in bin packing problems, we allow additive
constants and consider $(\alpha,\beta)$ as the asymptotic performance ratios.
We prove that for $\eps>0$, if we desire small $\alpha$, no scheme can beat
$(1+\eps, \Omega(1/\eps))$-approximate allocations and similarly as we desire
small $\beta$, no scheme can beat $(1.69103, 1+\eps)$-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+\eps, 1.7)$-approximate
allocations.
