@inproceedings{9528baff6e604ea3a5f72845acb7896e,

title = "On-line bin-stretching",

abstract = "We are given a sequence of items that can be packed into m unit size bins. In the classical bin packing problem we x 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 x 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.",

keywords = "Approximation algorithms, Bin-packing, Bin-stretching, Load balancing, On-line algorithms, Scheduling",

author = "Yossi Azar and Oded Regev",

note = "Funding Information: E-mail addresses: azar@math.tau.ac.il (Y. Azar), odedr@math.tau.ac.il (O. Regev). 1Research supported in part by the Israel Science Foundation and by the US-Israel Binational Science Foundation (BSF). Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1998. Copyright: Copyright 2016 Elsevier B.V., All rights reserved.; 2nd International Workshop on Randomization and Approximation Techniques in Computer Science, Random 1998 ; Conference date: 08-10-1998 Through 10-10-1998",

year = "1998",

doi = "10.1007/3-540-49543-6_7",

language = "English (US)",

isbn = "354065142X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "71--81",

editor = "Maria Serna and Rolim, {Jos{\'e} D.P} and Michael Luby",

booktitle = "Randomization and Approximation Techniques in Computer Science - 2nd International Workshop, RANDOM 1998, Proceedings",

}