On-line sequential bin packing
Andras Gyorgy, Gábor Lugosi and Gyorgy Ottucsak
In: 21st Annual Conference on Learning Theory (COLT 2008), 9-12 July 1999, Helsinki, Finland.
We consider a sequential version of the classical bin packing problem in which items are received one by one. Before the size of the next item is revealed, the decision maker needs to decide whether the next item is packed in the currently open bin or the bin is closed and a new bin is opened. If the new item does not fit, it is lost. If a bin is closed, the remaining free space in the bin accounts for a loss. The goal of the decision maker is to minimize the loss accumulated over n periods. The main result of the paper is an algorithm that has a cumulative loss not much larger than any strategy that uses a fixed threshold at each step to decide whether a new bin is opened.