On-line bin-stretching

Yossi Azar; Oded Regev

doi:10.1007/3-540-49543-6_7

On-line bin-stretching

Yossi Azar, Oded Regev

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Randomization and Approximation Techniques in Computer Science - 2nd International Workshop, RANDOM 1998, Proceedings
Editors	Maria Serna, José D.P Rolim, Michael Luby
Publisher	Springer Verlag
Pages	71-81
Number of pages	11
ISBN (Print)	354065142X, 9783540651420
DOIs	https://doi.org/10.1007/3-540-49543-6_7
State	Published - 1998
Event	2nd International Workshop on Randomization and Approximation Techniques in Computer Science, Random 1998 - Barcelona, Spain Duration: Oct 8 1998 → Oct 10 1998

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1518
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	2nd International Workshop on Randomization and Approximation Techniques in Computer Science, Random 1998
Country/Territory	Spain
City	Barcelona
Period	10/8/98 → 10/10/98

Keywords

Approximation algorithms
Bin-packing
Bin-stretching
Load balancing
On-line algorithms
Scheduling

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-49543-6_7

Cite this

Azar, Y., & Regev, O. (1998). On-line bin-stretching. In M. Serna, J. D. P. Rolim, & M. Luby (Eds.), Randomization and Approximation Techniques in Computer Science - 2nd International Workshop, RANDOM 1998, Proceedings (pp. 71-81). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1518). Springer Verlag. https://doi.org/10.1007/3-540-49543-6_7

On-line bin-stretching. / Azar, Yossi; Regev, Oded.
Randomization and Approximation Techniques in Computer Science - 2nd International Workshop, RANDOM 1998, Proceedings. ed. / Maria Serna; José D.P Rolim; Michael Luby. Springer Verlag, 1998. p. 71-81 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1518).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Azar, Y & Regev, O 1998, On-line bin-stretching. in M Serna, JDP Rolim & M Luby (eds), Randomization and Approximation Techniques in Computer Science - 2nd International Workshop, RANDOM 1998, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1518, Springer Verlag, pp. 71-81, 2nd International Workshop on Randomization and Approximation Techniques in Computer Science, Random 1998, Barcelona, Spain, 10/8/98. https://doi.org/10.1007/3-540-49543-6_7

Azar Y, Regev O. On-line bin-stretching. In Serna M, Rolim JDP, Luby M, editors, Randomization and Approximation Techniques in Computer Science - 2nd International Workshop, RANDOM 1998, Proceedings. Springer Verlag. 1998. p. 71-81. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-49543-6_7

Azar, Yossi ; Regev, Oded. / On-line bin-stretching. Randomization and Approximation Techniques in Computer Science - 2nd International Workshop, RANDOM 1998, Proceedings. editor / Maria Serna ; José D.P Rolim ; Michael Luby. Springer Verlag, 1998. pp. 71-81 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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: [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). 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",

}

TY - GEN

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). Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1998. Copyright: Copyright 2016 Elsevier B.V., All rights reserved.

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Bin-packing

KW - Bin-stretching

KW - Load balancing

KW - On-line algorithms

KW - Scheduling

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

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

U2 - 10.1007/3-540-49543-6_7

DO - 10.1007/3-540-49543-6_7

M3 - Conference contribution

AN - SCOPUS:77955834557

SN - 354065142X

SN - 9783540651420

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 71

EP - 81

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

A2 - Serna, Maria

A2 - Rolim, José D.P

A2 - Luby, Michael

PB - Springer Verlag

T2 - 2nd International Workshop on Randomization and Approximation Techniques in Computer Science, Random 1998

Y2 - 8 October 1998 through 10 October 1998

ER -

On-line bin-stretching

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this