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/3,...,j/k} ) for sufficiently large k when j = ak and 0.66 <= a < 2/3. Our results extend to continuous skewed distributions, where items are drawn uniformly on [0,a], for the same range. This implies that the expected asymptotic performance ratio of Best Fit is strictly greater than 1 for these distributions.
To appear in FOCS 2000.