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 whi
le 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 an
alysis 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.