TY - JOUR

T1 - On-line bin-stretching

AU - Azar, Yossi

AU - Regev, Oded

N1 - Funding Information:
E-mail addresses: [email protected] (Y. Azar), [email protected] (O. Regev). 1Research supported in part by the Israel Science Foundation and by the US-Israel Binational Science Foundation (BSF).

PY - 2001/10/6

Y1 - 2001/10/6

N2 - 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 m 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≥2. 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.

AB - 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 m 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≥2. 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.

KW - Approximation algorithms

KW - Bin stretching

KW - Bin-packing

KW - Load balancing

KW - On-line algorithms

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=0035818334&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035818334&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(00)00258-9

DO - 10.1016/S0304-3975(00)00258-9

M3 - Conference article

AN - SCOPUS:0035818334

SN - 0304-3975

VL - 268

SP - 17

EP - 41

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

T2 - On-line Algorithms'98 (OLA'98)

Y2 - 31 August 1998 through 5 September 1998

ER -