On-line bin-stretching

We are given a sequence of items that can be packed into m unit size bins. In the classical bin packing problem we fix the size of the bins and try to pack the items in the minimum number of such bins. In contrast, in the bin-stretching problem we fix the number of bins and try to pack the items while stretching the size of the bins as least as possible. We present two on-line algorithms for the bin-stretching problem that guarantee a stretching factor of 5/3 for any number ni of bins. We then combine the two algorithms and design an algorithm whose stretching factor is 1.625 for any m. The analysis for the performance of this algorithm is tight. The best lower bound for any algorithm is 4/3 for any m greater than or equal to2. We note that the bin-stretching problem is also equivalent to the classical scheduling (load balancing) problem in which the value of the makespan (maximum load) is known in advance. (C) 2001 Elsevier Science B.V. All rights reserved.