Online bin packing

Items arrive one at a time and must be placed into fixed-capacity bins. An online algorithm makes decisions without knowing later items. Heuristics may perform well on selected distributions without improving a worst-case guarantee.

In online one-dimensional bin packing, each item has a size and must be assigned to a bin of fixed capacity when it arrives. The algorithm cannot rearrange earlier assignments or see future items. Good choices depend on whether the goal is a worst-case guarantee or good performance on a particular distribution.

A competitive ratio compares an online algorithm with an optimal packing that knows the whole sequence. An empirical benchmark instead compares observed bin counts on selected instances. Better average performance on a benchmark is useful, but does not by itself imply an improved competitive ratio.