{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T19:03:47Z","timestamp":1794337427850,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540649175","type":"print"},{"value":"9783540683117","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0029578","type":"book-chapter","created":{"date-parts":[[2005,12,6]],"date-time":"2005-12-06T09:47:06Z","timestamp":1133862426000},"page":"385-394","source":"Crossref","is-referenced-by-count":9,"title":["Competitive odds and ends"],"prefix":"10.1007","author":[{"given":"Amos","family":"Fiat","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,11,22]]},"reference":[{"key":"17_CR1","unstructured":"H. Aborzi, E. Torng, P. Uthaisombut, and S. Wagner. The k-client problem. In Proc. of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 73\u201382, 1997."},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Aspnes, C. Dwork, and O. Waarts. A theory of competitive analysis for distributed algorithms. In Proc. 35th Symp. of Foundations of Computer Science, pages 401\u2013411, 1994.","DOI":"10.1109\/SFCS.1994.365676"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"M. Andrews, B. Awerbuch, A. Fern\u00e1ndez, J. Kleinberg, T. Leighton, and Z. Liu. Universal stability results for greedy contention-resolution protocols. In Proc. 37th IEEE Symposium on Foundations of Computer Science, pages 380\u2013389, 1996.","DOI":"10.1109\/SFCS.1996.548497"},{"key":"17_CR4","unstructured":"B. Awerbuch, Y. Bartal, and A. Fiat. Distributed paging for general networks. In Proceedings of the 7th Annual ACM-SIAM Symp. on Discrete Algorithms, pages 574\u2013583, 1996."},{"key":"17_CR5","unstructured":"Y. Azar, A. Broder, and M. Manasse. On-line choice of on-line algorithms. In Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, pages 432\u2013440, 1993."},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proc. 37th IEEE Symposium on Foundations of Computer Science, pages 184\u2013193, 1996.","DOI":"10.1109\/SFCS.1996.548477"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Y. Bartal, A. Blum, C. Burch, and A. Tomkins. A polylog(n)-competitive algorithm for metrical task systems. In Proceedings of the 29th annual ACM symposium on theory of computing, pages 711\u2013719, 1997.","DOI":"10.1145\/258533.258667"},{"key":"17_CR8","unstructured":"Y. Bartal, M. Charikar, and P. Indyk. On page migration and other relaxed task systems. In Proc. of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 43\u201352, 1997."},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"A. Blum, H. Karloff, Y. Rabani, and M. Saks. A decomposition theorem and lower bounds for randomized server problems. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 197\u2013207, 1992.","DOI":"10.1109\/SFCS.1992.267772"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Raghavan, and B. Schieber. Navigating in unfamiliar geometric terrain. In Lyle A. McGeoch and Daniel D. Sleator, editors, On-line Algorithms, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 151\u2013156. AMS\/ACM, February 1991.","DOI":"10.1145\/103418.103419"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"A. Borodin, S. Irani, P. Raghavan, and B. Schieber. Competitive paging with locality of reference. In Proc. 23rd ACM Symposium on Theory of Computing, pages 249\u2013259, 1991.","DOI":"10.1145\/103418.103422"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, and D.P. Williamson. Adversarial queueing theory. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1997.","DOI":"10.1145\/237814.237984"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task systems. In Proc. 19th Annual ACM Symposium on Theory of Computing, pages 373\u2013382, 1987.","DOI":"10.1145\/28395.28435"},{"key":"17_CR14","unstructured":"W.R. Burley and S. Irani. On algorithm design for metrical task systems. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 420\u2013429, 1995."},{"key":"17_CR15","unstructured":"M. Charikar, D. Halperin, and R. Motwani. The dynamic servers problem. In Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 410\u2013419, 1998."},{"key":"17_CR16","unstructured":"X. Deng and C.H. Papadimitriou. Competitive distributed decision making. In International Federation for Infomation Processing, A-12, pages 250\u2013256, 1992."},{"key":"17_CR17","unstructured":"E. Feuerstein. On-line pagine of Structured Data and Multi-threaded Paging. PhD thesis, University of Rome, 1995."},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"A. Fiat, D. Foster, H. Karloff, Y. Rabani, Y. Ravid, and S. Vishwanathan. Competitive algorithms for layered graph traversal. In Proc. 32nd IEEE Symposium on Foundations of Computer Science, pages 288\u2013297, 1991.","DOI":"10.1109\/SFCS.1991.185381"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(94)90154-6","volume":"130","author":"A. Fiat","year":"1994","unstructured":"A. Fiat and M. Ricklin. Competitive algorithms for the weighted server problem. In Theoretical Computer Science, volume 130, pages 85\u201399, 1994.","journal-title":"Theoretical Computer Science"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"S. Irani and Y. Rabani. On the value of information in coordination games. In Proc. 34th IEEE Symposium on Foundations of Computer Science, 1993.","DOI":"10.1109\/SFCS.1993.366886"},{"issue":"3","key":"17_CR21","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1137\/S0097539794261428","volume":"25","author":"S. Irani","year":"1996","unstructured":"S. Irani and Y. Rabani. On the value of coordination in distributed decision making. SIAM J. Comput., 25(3):498\u2013519, 1996.","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"17_CR22","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0304-3975(97)00006-6","volume":"194","author":"S. Irani","year":"1998","unstructured":"S. Irani and S.S. Seiden. Randomized algorithms for metrical task systems. Theoretical Computer Science, 194(1\u20132):163\u2013182, March 1998.","journal-title":"Theoretical Computer Science"},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram and K. Pruhs. Speed is as powerful as clairvoyance. In Proc. 36th IEEE Symposium on Foundations of Computer Science, pages 214\u2013221, 1995.","DOI":"10.1109\/SFCS.1995.492478"},{"key":"17_CR24","unstructured":"A.R. Karlin, M.S. Manasse, L.A. McGeoch, and S. Owicki. Competitive randomized algorithms for non-uniform problems. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, 1990."},{"key":"17_CR25","doi-asserted-by":"crossref","unstructured":"H. Karloff, Y. Rabani, and Y. Ravid. Lower bounds for randomized k-server and motion planning algorithms. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 278\u2013288, 1991.","DOI":"10.1145\/103418.103450"},{"key":"17_CR26","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias and C.H. Papadimitriou. Beyond competitive analysis. In Proc. 35th IEEE Symposium on Foundations of Computer Science, pages 394\u2013400, 1994.","DOI":"10.1109\/SFCS.1994.365677"},{"key":"17_CR27","unstructured":"S. Leonardi, A. Marchetti-Spaccamela, A. Presciutti, and A. Rosen. On-line randomized call control revisited. In Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 323\u2013332, 1998."},{"key":"17_CR28","unstructured":"C. Lund and N. Reingold. Linear programs for randomized on-line algorithms. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 382\u2013391, 1994."},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky and Y. Rabani. Universal o(congenstion+dilation+log1+\u03b5 n) local control packet switching algorithms. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 644\u2013653, 1997.","DOI":"10.1145\/258533.258659"},{"key":"17_CR30","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou and M. Yannakakis. Linear programming without the matrix. In Proc. 25th ACM Symposium on Theory of Computing, San Diego, pages 121\u2013129, 1993.","DOI":"10.1145\/167088.167127"},{"key":"17_CR31","doi-asserted-by":"crossref","unstructured":"C.A. Phillips, C. Stein, E. Torng, and J. Wein. Optimal time-critical scheduling via resource augmentation. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 140\u2013149, 1997.","DOI":"10.1145\/258533.258570"},{"key":"17_CR32","doi-asserted-by":"crossref","unstructured":"Y. Rabani and E. Tardos. Distributed packet switching in arbitrary networks. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 366\u2013367, 1996.","DOI":"10.1145\/237814.237983"},{"key":"17_CR33","unstructured":"N.E. Young. On-line caching as cache size varies. In Proc. of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 241\u2013250, 1991."},{"issue":"6","key":"17_CR34","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"N.E. Young","year":"1994","unstructured":"N.E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525\u2013541, 1994.","journal-title":"Algorithmica"},{"key":"17_CR35","unstructured":"N.E. Young. On-line file caching. In Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 82\u201386, 1998."}],"container-title":["Lecture Notes in Computer Science","Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029578","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T03:46:46Z","timestamp":1736135206000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029578"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540649175","9783540683117"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/bfb0029578","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0029561","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}