####
Linear waste of best fit bin packing on skewed distributions.

We prove that Best Fit bin packing has linear waste on the
discrete distribution U{j, k} (where items are drawn uniformly from
the set {1/k, 2/k,... , j/k}) for sufficiently large k when j = k and
0.66 < 2/3. Our results extend to continuous skewed distributions,
where items are drawn uniformly on [0, a], for 0.66 a < 2/3. This
implies that the expected asymptotic performance ratio of Best Fit is
strictly greater than 1 for these distributions.