New on-line algorithms for the page replication problem

Susanne Albers; Hisashi Koga

doi:10.1007/3-540-58218-5_3

New on-line algorithms for the page replication problem

Susanne Albers, Hisashi Koga

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

3 Scopus citations

Abstract

We present improved competitive on-line algorittmls for the page replication problem and concentrate on important network topologies for which algorithms with a constant competitive factor can be given. We develop an optional randomized on-line replication algorithm for trees and uniform networks; its competitive factor is approximately 1.58. Furthermore we consider on-llne replication algorithms for rings and present general techniques that transform large classes of c-competltlve algorithms for trees into 2c-competitive algorithms for rings. As a result we obtain a randomized on-line algorithm for rings that is 3.16-competitive. We also derive two 4-competitive on-line algorithms for rings which are either deterministic or memoryless.

Original language	English
Title of host publication	Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings
Editors	Erik M. Schmidt, Sven Skyum
Publisher	Springer Verlag
Pages	25-36
Number of pages	12
ISBN (Print)	9783540582182
DOIs	https://doi.org/10.1007/3-540-58218-5_3
State	Published - 1994
Externally published	Yes
Event	4th Scandinavian Workshop on Algorithm Theory, SWAT 1994 - Aarhus, Denmark Duration: 6 Jul 1994 → 8 Jul 1994

Publication series

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

Conference

Conference	4th Scandinavian Workshop on Algorithm Theory, SWAT 1994
Country/Territory	Denmark
City	Aarhus
Period	6/07/94 → 8/07/94

Access to Document

10.1007/3-540-58218-5_3

Cite this

Albers, S., & Koga, H. (1994). New on-line algorithms for the page replication problem. In E. M. Schmidt, & S. Skyum (Eds.), Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings (pp. 25-36). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 824 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-58218-5_3

Albers, Susanne ; Koga, Hisashi. / New on-line algorithms for the page replication problem. Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings. editor / Erik M. Schmidt ; Sven Skyum. Springer Verlag, 1994. pp. 25-36 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d5368baa2cde4ac68ebcc4d22337e949,

title = "New on-line algorithms for the page replication problem",

abstract = "We present improved competitive on-line algorittmls for the page replication problem and concentrate on important network topologies for which algorithms with a constant competitive factor can be given. We develop an optional randomized on-line replication algorithm for trees and uniform networks; its competitive factor is approximately 1.58. Furthermore we consider on-llne replication algorithms for rings and present general techniques that transform large classes of c-competltlve algorithms for trees into 2c-competitive algorithms for rings. As a result we obtain a randomized on-line algorithm for rings that is 3.16-competitive. We also derive two 4-competitive on-line algorithms for rings which are either deterministic or memoryless.",

author = "Susanne Albers and Hisashi Koga",

year = "1994",

doi = "10.1007/3-540-58218-5_3",

language = "English",

isbn = "9783540582182",

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

publisher = "Springer Verlag",

pages = "25--36",

editor = "Schmidt, {Erik M.} and Sven Skyum",

booktitle = "Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings",

}

Albers, S & Koga, H 1994, New on-line algorithms for the page replication problem. in EM Schmidt & S Skyum (eds), Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 824 LNCS, Springer Verlag, pp. 25-36, 4th Scandinavian Workshop on Algorithm Theory, SWAT 1994, Aarhus, Denmark, 6/07/94. https://doi.org/10.1007/3-540-58218-5_3

New on-line algorithms for the page replication problem. / Albers, Susanne; Koga, Hisashi.
Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings. ed. / Erik M. Schmidt; Sven Skyum. Springer Verlag, 1994. p. 25-36 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 824 LNCS).

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

TY - GEN

T1 - New on-line algorithms for the page replication problem

AU - Albers, Susanne

AU - Koga, Hisashi

PY - 1994

Y1 - 1994

N2 - We present improved competitive on-line algorittmls for the page replication problem and concentrate on important network topologies for which algorithms with a constant competitive factor can be given. We develop an optional randomized on-line replication algorithm for trees and uniform networks; its competitive factor is approximately 1.58. Furthermore we consider on-llne replication algorithms for rings and present general techniques that transform large classes of c-competltlve algorithms for trees into 2c-competitive algorithms for rings. As a result we obtain a randomized on-line algorithm for rings that is 3.16-competitive. We also derive two 4-competitive on-line algorithms for rings which are either deterministic or memoryless.

AB - We present improved competitive on-line algorittmls for the page replication problem and concentrate on important network topologies for which algorithms with a constant competitive factor can be given. We develop an optional randomized on-line replication algorithm for trees and uniform networks; its competitive factor is approximately 1.58. Furthermore we consider on-llne replication algorithms for rings and present general techniques that transform large classes of c-competltlve algorithms for trees into 2c-competitive algorithms for rings. As a result we obtain a randomized on-line algorithm for rings that is 3.16-competitive. We also derive two 4-competitive on-line algorithms for rings which are either deterministic or memoryless.

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

U2 - 10.1007/3-540-58218-5_3

DO - 10.1007/3-540-58218-5_3

M3 - Conference contribution

AN - SCOPUS:84968322750

SN - 9783540582182

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

SP - 25

EP - 36

BT - Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Schmidt, Erik M.

A2 - Skyum, Sven

PB - Springer Verlag

T2 - 4th Scandinavian Workshop on Algorithm Theory, SWAT 1994

Y2 - 6 July 1994 through 8 July 1994

ER -

Albers S, Koga H. New on-line algorithms for the page replication problem. In Schmidt EM, Skyum S, editors, Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings. Springer Verlag. 1994. p. 25-36. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-58218-5_3

New on-line algorithms for the page replication problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this