On-line load balancing for related machines

Piotr Berman; Moses Charikar; Marek Karpinski

doi:10.1007/3-540-63307-3_52

On-line load balancing for related machines

Piotr Berman, Moses Charikar, Marek Karpinski

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

16 Scopus citations

Abstract

We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + √8 ≈ 5.828 for the deterministic version, and 3.31/ln 2.155 ≈ 4.311 for its randomized variant, improving the previous competitive ratios of 8 and 2e ≈ 5.436. We also prove lower bounds of 2.4380 on the competitive ratio of deterministic algorithms and 1.8372 on the competitive ratio of randomized algorithms for this problem.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings
Editors	Frank Dehne, Jorg-Rudiger Sack, Andrew Rau-Chaplin, Roberto Tamassia
Publisher	Springer Verlag
Pages	116-125
Number of pages	10
ISBN (Print)	3540633073, 9783540633075
DOIs	https://doi.org/10.1007/3-540-63307-3_52
State	Published - 1997
Event	5th International Workshop on Algorithms and Data Structures, WADS 1997 - Halifax, Canada Duration: Aug 6 1997 → Aug 8 1997

Publication series

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

Other

Other	5th International Workshop on Algorithms and Data Structures, WADS 1997
Country/Territory	Canada
City	Halifax
Period	8/6/97 → 8/8/97

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-63307-3_52

Cite this

Berman, P., Charikar, M., & Karpinski, M. (1997). On-line load balancing for related machines. In F. Dehne, J.-R. Sack, A. Rau-Chaplin, & R. Tamassia (Eds.), Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings (pp. 116-125). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1272). Springer Verlag. https://doi.org/10.1007/3-540-63307-3_52

Berman, Piotr ; Charikar, Moses ; Karpinski, Marek. / On-line load balancing for related machines. Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Andrew Rau-Chaplin ; Roberto Tamassia. Springer Verlag, 1997. pp. 116-125 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{77a971c2f2fc45aea11884de0d1cdace,

title = "On-line load balancing for related machines",

abstract = "We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + √8 ≈ 5.828 for the deterministic version, and 3.31/ln 2.155 ≈ 4.311 for its randomized variant, improving the previous competitive ratios of 8 and 2e ≈ 5.436. We also prove lower bounds of 2.4380 on the competitive ratio of deterministic algorithms and 1.8372 on the competitive ratio of randomized algorithms for this problem.",

author = "Piotr Berman and Moses Charikar and Marek Karpinski",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 5th International Workshop on Algorithms and Data Structures, WADS 1997 ; Conference date: 06-08-1997 Through 08-08-1997",

year = "1997",

doi = "10.1007/3-540-63307-3_52",

language = "English (US)",

isbn = "3540633073",

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

publisher = "Springer Verlag",

pages = "116--125",

editor = "Frank Dehne and Jorg-Rudiger Sack and Andrew Rau-Chaplin and Roberto Tamassia",

booktitle = "Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings",

address = "Germany",

}

Berman, P, Charikar, M & Karpinski, M 1997, On-line load balancing for related machines. in F Dehne, J-R Sack, A Rau-Chaplin & R Tamassia (eds), Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1272, Springer Verlag, pp. 116-125, 5th International Workshop on Algorithms and Data Structures, WADS 1997, Halifax, Canada, 8/6/97. https://doi.org/10.1007/3-540-63307-3_52

On-line load balancing for related machines. / Berman, Piotr; Charikar, Moses; Karpinski, Marek.
Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Andrew Rau-Chaplin; Roberto Tamassia. Springer Verlag, 1997. p. 116-125 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1272).

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

TY - GEN

T1 - On-line load balancing for related machines

AU - Berman, Piotr

AU - Charikar, Moses

AU - Karpinski, Marek

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1997.

PY - 1997

Y1 - 1997

N2 - We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + √8 ≈ 5.828 for the deterministic version, and 3.31/ln 2.155 ≈ 4.311 for its randomized variant, improving the previous competitive ratios of 8 and 2e ≈ 5.436. We also prove lower bounds of 2.4380 on the competitive ratio of deterministic algorithms and 1.8372 on the competitive ratio of randomized algorithms for this problem.

AB - We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + √8 ≈ 5.828 for the deterministic version, and 3.31/ln 2.155 ≈ 4.311 for its randomized variant, improving the previous competitive ratios of 8 and 2e ≈ 5.436. We also prove lower bounds of 2.4380 on the competitive ratio of deterministic algorithms and 1.8372 on the competitive ratio of randomized algorithms for this problem.

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

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

U2 - 10.1007/3-540-63307-3_52

DO - 10.1007/3-540-63307-3_52

M3 - Conference contribution

AN - SCOPUS:84938251689

SN - 3540633073

SN - 9783540633075

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

SP - 116

EP - 125

BT - Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Rau-Chaplin, Andrew

A2 - Tamassia, Roberto

PB - Springer Verlag

T2 - 5th International Workshop on Algorithms and Data Structures, WADS 1997

Y2 - 6 August 1997 through 8 August 1997

ER -

Berman P, Charikar M, Karpinski M. On-line load balancing for related machines. In Dehne F, Sack JR, Rau-Chaplin A, Tamassia R, editors, Algorithms and Data Structures - 5th International Workshop, WADS 1997, Proceedings. Springer Verlag. 1997. p. 116-125. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-63307-3_52

On-line load balancing for related machines

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this