{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:57:46Z","timestamp":1775282266508,"version":"3.50.1"},"reference-count":25,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1994,6,1]],"date-time":"1994-06-01T00:00:00Z","timestamp":770428800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6986,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[1994,6]]},"DOI":"10.1016\/s0022-0000(05)80060-1","type":"journal-article","created":{"date-parts":[[2005,8,20]],"date-time":"2005-08-20T07:18:35Z","timestamp":1124522315000},"page":"410-428","source":"Crossref","is-referenced-by-count":35,"title":["Competitive k-server algorithms"],"prefix":"10.1016","volume":"48","author":[{"given":"Amos","family":"Fiat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Rabani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yiftach","family":"Ravid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(05)80060-1_bib1","series-title":"Proceedings, 22nd Annu. ACM Symp. on Theory of Computing","first-page":"379","article-title":"On the power of randomization in on-line algorithms","author":"Ben-David","year":"1990"},{"key":"10.1016\/S0022-0000(05)80060-1_bib2","series-title":"Proceedings, 1st Annu. ACM-SIAM Symp. on Discrete Algorithms","first-page":"280","article-title":"A competitive three-server algorithm","author":"Berman","year":"1990"},{"key":"10.1016\/S0022-0000(05)80060-1_bib3","series-title":"Proceedings, 19th Annu. ACM Symp. on Theory of Computing","first-page":"373","article-title":"An optimal on-line algorithm for metrical task systems","author":"Borodin","year":"1987"},{"key":"10.1016\/S0022-0000(05)80060-1_bib4","article-title":"Searching with Uncertaincy","author":"Baeza-Yates","year":"1987"},{"key":"10.1016\/S0022-0000(05)80060-1_bib5","series-title":"Proceedings, 22nd Annu. ACM Symp. on Theory of Computing","first-page":"369","article-title":"Random walks on weighted graphs and applications to on-line algorithms","author":"Coppersmith","year":"1990"},{"issue":"No. 2","key":"10.1016\/S0022-0000(05)80060-1_bib6","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1137\/0404017","article-title":"New results on server problem","volume":"4","author":"Chrobak","year":"1991","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0022-0000(05)80060-1_bib7","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1137\/0220008","article-title":"An optimal on-line algorithm for the server problem on trees","volume":"20","author":"Chrobak","year":"1991","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(05)80060-1_bib8","series-title":"Proceedings, Mathematical Foundations of Computer Science, Bansk\u00e1 Bystrica, 1990","first-page":"607","article-title":"On fast algorithm for two servers","volume":"12","author":"Chrobak","year":"1991"},{"key":"10.1016\/S0022-0000(05)80060-1_bib9","series-title":"Proceedings, 32nd Annu. Symp. on Foundations of Comput. Sci.","first-page":"288","article-title":"Competitive algorithms for layered graph traversal","author":"Fiat","year":"1991"},{"key":"10.1016\/S0022-0000(05)80060-1_bib10","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","article-title":"Competitive paging algorithms","volume":"12","author":"Fiat","year":"1991","journal-title":"J. Algorithms"},{"key":"10.1016\/S0022-0000(05)80060-1_bib11","unstructured":"A. Fiat, Y. Rabani, Y. Ravid, and B. Schieber, A deterministic O(k3)-competitive k-server algorithm for the circle, manuscript."},{"key":"10.1016\/S0022-0000(05)80060-1_bib12","series-title":"Proceedings, 23nd Annu. ACM Symp. on Theory of Computing","first-page":"260","article-title":"The harmonic k-server algorithm is competitive","author":"Grove","year":"1991"},{"key":"10.1016\/S0022-0000(05)80060-1_bib13","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0020-0190(91)90160-J","article-title":"A competitive 2-server algorithm","volume":"39","author":"Irani","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0022-0000(05)80060-1_bib14","series-title":"A randomized (n + 1)k competitive algorithm on the graph","author":"Karp","year":"1989"},{"key":"10.1016\/S0022-0000(05)80060-1_bib15","series-title":"Proceedings, 1st Annu. ACM-SIAM Symp. on Discrete Algorithms","first-page":"301","article-title":"Competitive randomized algorithms for non-uniform problems","author":"Karlin","year":"1990"},{"issue":"1","key":"10.1016\/S0022-0000(05)80060-1_bib16","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF01762111","article-title":"Competitive Snoopy caching","volume":"3","author":"Karlin","year":"1988","journal-title":"Algorithmica"},{"key":"10.1016\/S0022-0000(05)80060-1_bib17_1","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","article-title":"Competitive algorithms for on-line problems","volume":"11","author":"Manasse","year":"1990","journal-title":"J. Algorithms"},{"key":"10.1016\/S0022-0000(05)80060-1_bib17_2","series-title":"Proceedings 20th Annu. ACM Symp. on Theory of Coputing","first-page":"322","year":"1988"},{"key":"10.1016\/S0022-0000(05)80060-1_bib18","doi-asserted-by":"crossref","unstructured":"L. A. McGeoch and D. D. Sleator, A strongly competitive randomized paging algorithm, Algorithmica, submitted.","DOI":"10.1007\/BF01759073"},{"key":"10.1016\/S0022-0000(05)80060-1_bib19","series-title":"Proceedings, 16th ICALP","first-page":"610","article-title":"Shortest paths without a map","author":"Papadimitriou","year":"1989"},{"key":"10.1016\/S0022-0000(05)80060-1_bib20","article-title":"Lecture Notes on Randomized Algorithms","author":"Raghavan","year":"1990"},{"key":"10.1016\/S0022-0000(05)80060-1_bib21_1","series-title":"Proceedings, 16th ICALP","article-title":"Memory versus randomization in on-line algorithms","author":"Raghavan","year":"1989"},{"key":"10.1016\/S0022-0000(05)80060-1_bib21_2","volume":"Vol. 372","year":"1992"},{"key":"10.1016\/S0022-0000(05)80060-1_bib22","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","article-title":"Amortized efficiency of list update and paging rules","volume":"28","author":"Sleator","year":"1985","journal-title":"Commun. ACM"},{"key":"10.1016\/S0022-0000(05)80060-1_bib23","article-title":"Recent Work on the Server Problem","author":"Turpin","year":"1989"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000005800601?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000005800601?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,17]],"date-time":"2019-03-17T12:41:16Z","timestamp":1552826476000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000005800601"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,6]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,6]]}},"alternative-id":["S0022000005800601"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(05)80060-1","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[1994,6]]}}}