{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:17:05Z","timestamp":1725484625379},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424932"},{"type":"electronic","value":"9783540446767"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44676-1_7","type":"book-chapter","created":{"date-parts":[[2007,5,18]],"date-time":"2007-05-18T12:43:15Z","timestamp":1179492195000},"page":"86-97","source":"Crossref","is-referenced-by-count":5,"title":["A General Decomposition Theorem for the k-Server Problem"],"prefix":"10.1007","author":[{"given":"Steven S.","family":"Seiden","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Bartal, Y. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (1996), pp. 183\u2013193.","DOI":"10.1109\/SFCS.1996.548477"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Bartal, Y. On approximating arbitrary metrics by tree metrics. In Proceedings of the 30th ACM Symposium on Theory of Computing (1998), pp. 161\u2013168.","DOI":"10.1145\/276698.276725"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Blum, A., Burch, C., AND Tomkins, A. A polylog(n)-competitive algorithm for metrical task systems. In Proceedings of the 29th ACM Symposium on Theory of Computing (1997), pp. 711\u2013719.","DOI":"10.1145\/258533.258667"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Bollobas, B., AND Mendel, M. Ramsey-type theorems for metric spaces and their application for metrical task systems. Manuscript, 2001.","DOI":"10.1109\/SFCS.2001.959914"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Chrobak, M., AND Larmore, L. L. A randomized algorithm for two servers on the line. Information and Computation 158, 1 (Apr 2000), 53\u201369.","DOI":"10.1006\/inco.1999.2809"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Bein, W., Chrobak, M., AND Larmore, L. The 3-server problem in the plane. In Proceedings of the 7th Annual European Symposium on Algorithms (Jul 1999), pp. 301\u2013312.","DOI":"10.1007\/3-540-48481-7_27"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Ben-David, S., Borodin, A., Karp, R., Tardos, G., AND Wigderson, A. On the power of randomization in on-line algorithms. Algorithmica 11,1 (Jan 1994), 2\u201314.","DOI":"10.1007\/BF01294260"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Blum, A., Burch, C., AND Kalai, A. Finely-competitive paging. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (1999), pp. 450\u2013457.","DOI":"10.1109\/SFFCS.1999.814617"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Blum, A., Karloff, H., Rabani, Y., AND Saks, M. A decomposition theorem for task systems and bounds for randomized server problems. SIAM Journal on Computing 30,5 (Dec 2000), 1624\u20131661.","DOI":"10.1137\/S0097539799351882"},{"key":"7_CR10","unstructured":"Borodin, A., AND El-Yaniv, R. Online Computation and Competitive Analysis. Cambridge University Press, 1998."},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Borodin, A., Linial, N., AND Saks, M. An optimal online algorithm for metrical task systems. Journal of the ACM 39,4 (Oct 1992), 745\u2013763.","DOI":"10.1145\/146585.146588"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Karloff, H., Payne, T., AND Vishwanathan, S. New results on server problems. SIAM Journal on Discrete Mathematics 4,2 (May 1991), 172\u2013181.","DOI":"10.1137\/0404017"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Hrobak, M., AND Larmore, L. An optimal on-line algorithm for k-servers on trees. SIAM Journal on Computing 20, 1 (Feb 1991), 144\u2013148.","DOI":"10.1137\/0220008"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Chrobak, M., AND Larmore, L. L. Server problems and on-line games. In Proceedings of the DIMACS Workshop on On-line Algorithms (Feb 1991), pp. 11\u201364.","DOI":"10.1090\/dimacs\/007\/02"},{"issue":"2","key":"7_CR15","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0020-0190(97)00099-9","volume":"63","author":"M. Chrobak","year":"1997","unstructured":"Chrobak, M., Larmore, L. L., Llund, C., AND Reingold, N. A better lower bound on the competitive ratio of the randomized 2-server problem. Information Processing Letters 63,2 (1997), 79\u201383.","journal-title":"Information Processing Letters"},{"issue":"4","key":"7_CR16","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A. Fiat","year":"1991","unstructured":"Fiat, A., Karp, R., Luby, M., Mgeoch, L., Sleator, D., AND Young, N. Competitive paging algorithms. Journal of Algorithms 12,4 (Dec 1991), 685\u2013699.","journal-title":"Journal of Algorithms"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Fiat, A., AND Mendel, M. Better algorithms for unfair metrical task systems and applications. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (May 2000), pp. 725\u2013734.","DOI":"10.1145\/335305.335408"},{"key":"7_CR18","series-title":"Lect Notes Comput Sci","volume-title":"On-Line Algorithms\u2014The State of the Art","year":"1998","unstructured":"Fiat, A., AND Woeginger, G., Eds. On-Line Algorithms\u2014The State of the Art. Lecture Notes in Computer Science. Springer-Verlag, 1998."},{"key":"7_CR19","unstructured":"Irani, S. Randomized weighted caching with two page weights. Manuscript, 1999."},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Karlin, A., Manasse, M., Mcgeoch, L., AND Owicki, S. Competitive randomized algorithms for nonuniform problems. Algorithmica 11,6 (Jun 1994), 542\u2013571.","DOI":"10.1007\/BF01189993"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Karloff, H., Rabani, Y., AND Ravid, Y. Lower bounds for randomized k-server and motion-planning algorithms. SIAM Journal on Computing 23,2 (Apr 1994), 293\u2013312.","DOI":"10.1137\/S0097539792224838"},{"key":"7_CR22","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E. Koutsoupias","year":"1995","unstructured":"Koutsoupias, E., AND Apadimitriou, C. On the k-server conjecture. Journal of the ACM 42 (1995), 971\u2013983.","journal-title":"Journal of the ACM"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., AND Papadimitriou, C. The 2-evader problem. Information Processing Letters 57,5 (Mar 1996), 249\u2013252.","DOI":"10.1016\/0020-0190(96)00010-5"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Manasse, M., Mcgeoch, L., AND Sleator, D. Competitive algorithms for server problems. Journal of Algorithms 11,2 (Jun 1990), 208\u2013230.","DOI":"10.1016\/0196-6774(90)90003-W"},{"issue":"6","key":"7_CR25","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1007\/BF01759073","volume":"6","author":"L. Mcgeoch","year":"1991","unstructured":"Mcgeoch, L., AND Sleator, D. A strongly competitive randomized paging algorithm. Algorithmica 6,6 (1991), 816\u2013825.","journal-title":"Algorithmica"},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Seiden, S. S. Unfair problems and randomized algorithms for metrical task systems. Information and Computation 148,2 (Feb 1999), 219\u2013240.","DOI":"10.1006\/inco.1998.2744"},{"key":"7_CR27","doi-asserted-by":"crossref","unstructured":"Sleator, D., AND Tarjan, R. Amortized efficiency of list update and paging rules. Communications of the ACM 28,2 (Feb 1985), 202\u2013208.","DOI":"10.1145\/2786.2793"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44676-1_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T00:44:21Z","timestamp":1556412261000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44676-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424932","9783540446767"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-44676-1_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}