A self-organizing bin packing heuristic

J. Csirik, D.S. Johnson, C. Kenyon, P.W. Shor and R.R. Weber, in Proceedings 1999 Workshop on Algorithmic Engineering and Experimentation, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1619, 246-265, 1999.

Abstract

This paper reports on experiments with a new on-line heuristic for
one-dimensional bin packing whose average-case behavior is
surprisingly robust. We restrict attention to the class of discrete
distributions, i.e., ones in which the set of possible item sizes is
finite (as is commonly the case in practical applications), and in
which all sizes and probabilities are rational. It is known from [7]
that for any such distribution the optimal expected waste grows either
as Theta(n), Theta(sqrt{n}), or O(1), Our new Sum of Squares algorithm
(SS) appears to have roughly the same expected behavior in all three
cases. This claim is experimentally evaluated using a
newly-discovered, linear-programming-based algorithm that determines
the optimal expected waste rate for any given discrete distribution in
pseudopolynomial time (the best one can hope for given that the basic
problem is NP-hard). Although SS appears to be essentially optimal
when the expected optimal waste rate is sublinear, it is less
impressive when the expected optimal waste rate is linear. The
expected ratio of the number of bins used by SS to the optimal number
appears to go to 1 asymptotically in the first case, whereas there are
distributions for which it can be as high as 1.5 in the
second. However, by modifying the algorithm slightly, using a single
parameter that is tunable to the distribution in question (either by
advanced knowledge or by on-line learning), we appear to be able to
make the ratio go to 1 in all cases.

back to list of papers