Bin Stretching

Online Bin Stretching is a semi-online variant of the well-studied assignment problem Bin Packing. In 1998, Azar and Regev initiated the study of the following algorithmic problem. An (online) algorithm is presented with an input of items with sizes between 0 and 1, which are revealed one by one. Before the next item is revealed the algorithm must decide in which bin the item should be packed. In advance, the algorithm has access to the information that the complete input can be packed in m bins of size 1. In general, we are allowed to use at most m bins of capacity α≥1. Our goal is to minimize the stretching factor α.