{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,24]],"date-time":"2026-10-24T02:25:38Z","timestamp":1792808738232,"version":"4.5.0"},"reference-count":15,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[1991,5]]},"abstract":"<jats:p>In the k-server problem, one must choose how k mobile servers will serve each of a sequence of requests, making decisions in an online manner. An optimal deterministic online strategy is exhibited when the requests fall on the real line. For the weighted-cache problem, in which the cost of moving to x from any other point is $w( x )$, the weight of x, an optimal deterministic algorithm is also provided. The nonexistence of competitive algorithms for the asymmetric two-server problem and of memoryless algorithms for the weighted-cache problem is proved. A fast algorithm for oflline computing of an optimal schedule is given, and it is shown that finding an optimal offline schedule is at least as hard as the assignment problem.<\/jats:p>","DOI":"10.1137\/0404017","type":"journal-article","created":{"date-parts":[[2005,2,23]],"date-time":"2005-02-23T08:03:04Z","timestamp":1109145784000},"page":"172-181","source":"Crossref","is-referenced-by-count":169,"title":["New Ressults on Server Problems"],"prefix":"10.1137","volume":"4","author":[{"given":"M.","family":"Chrobak","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"H.","family":"Karloof","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"T.","family":"Payne","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Vishwnathan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, Lower bounds for algebraic computation trees, Proc. 15th ACM Symposium on Theory of Computing, 1983, 80\u201386","DOI":"10.1145\/800061.808735"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"A. Borodin, N. Linial, M. Saks, An optimal online algorithm for metrical task systems, Proc. 19th ACM Symposium on Theory of Computing, 1987, 373\u2013382","DOI":"10.1145\/28395.28435"},{"key":"R3","unstructured":"A. Borodin, personal communication"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.4.585"},{"key":"R5","unstructured":"B. Chlebus, University of California, Riverside, CA, personal communication"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"D. Coppersmith, P. G. Doyle, P. Raghavan, M. Snir, Random walks on weighted graphs, with applications to on-line algorithms, Proc. 22nd ACM Symposium on Theory of Computing, Baltimore, 1990, 369\u2013378","DOI":"10.1145\/100216.100266"},{"key":"R7","unstructured":"A. Fiat, R. karp, M. Luby, L. A. McGeoch, D. Sleator, N. E. Young, Competitive paging algorithms, Technical report, CMU-CS-88-196, Computer Science Department, Carnegie\u2013Mellon University, 1988"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90160-J"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762111"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"M. Manasse, L. A. McGeoch, D. Sleator, Competitve algorithms for online problems, Proc. 20th ACM Symposium on Theory of Computing, 1988, 322\u2013333","DOI":"10.1145\/62212.62243"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759073"},{"key":"R13","unstructured":"P. Raghavan, M. Snir, Memory versus randomization in online algorithms, Technical Report, RC 15622, IBM Research Report, 1990, March"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0404017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:15:37Z","timestamp":1787318137000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0404017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,5]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,5]]}},"alternative-id":["10.1137\/0404017"],"URL":"https:\/\/doi.org\/10.1137\/0404017","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,5]]}}}