{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:08Z","timestamp":1763467988092,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_25","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"287-298","source":"Crossref","is-referenced-by-count":10,"title":["Metrical Task Systems and the k-Server Problem on HSTs"],"prefix":"10.1007","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[]},{"given":"Niv","family":"Buchbinder","sequence":"additional","affiliation":[]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"25_CR1","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0304-3975(98)00116-9","volume":"234","author":"D. Achlioptas","year":"2000","unstructured":"Achlioptas, D., Chrobak, M., Noga, J.: Competitive analysis of randomized paging algorithms. Theory Computer Science\u00a0234(1-2), 203\u2013218 (2000)","journal-title":"Theory Computer Science"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Buchbinder, N., Naor, J.S.: A primal-dual randomized algorithm for weighted paging. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 507\u2013517 (2007)","DOI":"10.1109\/FOCS.2007.43"},{"key":"25_CR3","unstructured":"Bansal, N., Buchbinder, N., Naor, S.: Towards the randomized k-server conjecture: A primal-dual approach. In: ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 (to appear, 2010)"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Buchbinder, N., Naor, J.(S).: Randomized competitive algorithms for generalized caching. In: Proceedings of the 40th annual ACM symposium on Theory of computing, pp. 235\u2013244 (2008)","DOI":"10.1145\/1374376.1374412"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Blum, A., Burch, C., Tomkins, A.: A polylog(n)-competitive algorithm for metrical task systems. In: Proceedings of the 29th Annual ACM Symposium on Theory of computing, pp. 711\u2013719 (1997)","DOI":"10.1145\/258533.258667"},{"key":"25_CR6","unstructured":"Blum, A.: Personal communication"},{"issue":"1","key":"25_CR7","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1023\/A:1007621832648","volume":"39","author":"A. Blum","year":"2000","unstructured":"Blum, A., BurchP, C.: On-line learning and the metrical task system problem. Machine Learning\u00a039(1), 35\u201358 (2000)","journal-title":"Machine Learning"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Blum, A., Burch, C., Kalai, A.: Finely-competitive paging. In: IEEE Symposium on Foundations of Computer Science, pp. 450\u2013458 (1999)","DOI":"10.1109\/SFFCS.1999.814617"},{"key":"25_CR9","volume-title":"Online computation and competitive analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"4","key":"25_CR10","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"A. Borodin","year":"1992","unstructured":"Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task system. Journal of the ACM\u00a039(4), 745\u2013763 (1992)","journal-title":"Journal of the ACM"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing problems. In: Proceedings of the 13th Annual European Symposium on Algorithms (2005)","DOI":"10.1007\/11561071_61"},{"issue":"2-3","key":"25_CR12","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science\u00a03(2-3), 93\u2013263 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"issue":"2","key":"25_CR13","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/0404017","volume":"4","author":"M. Chrobak","year":"1991","unstructured":"Chrobak, M., Karloff, H., Payne, T., Vishwanathan, S.: New results on server problems. SIAM Journal on Discrete Math\u00a04(2), 172\u2013181 (1991)","journal-title":"SIAM Journal on Discrete Math"},{"issue":"1","key":"25_CR14","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1137\/0220008","volume":"20","author":"M. Chrobak","year":"1991","unstructured":"Chrobak, M., Larmore, L.: An optimal on-line algorithm for k-servers on trees. SIAM Journal on Computing\u00a020(1), 144\u2013148 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"Cot\u00e9, A., Meyerson, A., Poplawski, L.: Randomized k-server on hierarchical binary trees. In: STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing, pp. 227\u2013234 (2008)","DOI":"10.1145\/1374376.1374411"},{"issue":"1","key":"25_CR16","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1002\/rsa.20124","volume":"29","author":"B. Csaba","year":"2006","unstructured":"Csaba, B., Lodha, S.: A randomized on-line algorithm for the k-server problem on a line. Random Structures and Algorithms\u00a029(1), 82\u2013104 (2006)","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"25_CR17","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.M., Luby, M., McGeoch, L.A., Sleator, D.D., Young, N.E.: Competitive paging algorithms. Journal of Algorithms\u00a012(4), 685\u2013699 (1991)","journal-title":"Journal of Algorithms"},{"issue":"6","key":"25_CR18","doi-asserted-by":"publisher","first-page":"1403","DOI":"10.1137\/S0097539700376159","volume":"32","author":"A. Fiat","year":"2003","unstructured":"Fiat, A., Mendel, M.: Better algorithms for unfair metrical task systems and applications. SIAM Journal on Computing\u00a032(6), 1403\u20131422 (2003)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"25_CR19","doi-asserted-by":"publisher","first-page":"1403","DOI":"10.1137\/S0097539700376159","volume":"32","author":"A. Fiat","year":"2003","unstructured":"Fiat, A., Mendel, M.: Better algorithms for unfair metrical task systems and applications. SIAM Journal on Computing\u00a032(6), 1403\u20131422 (2003)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"25_CR20","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1007\/s00453-001-0095-6","volume":"32","author":"S. Irani","year":"2002","unstructured":"Irani, S.: Randomized weighted caching with two page weights. Algorithmica\u00a032(4), 624\u2013640 (2002)","journal-title":"Algorithmica"},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"Irani, S.: Page replacement with multi-size pages and applications to web caching. In: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 701\u2013710 (1997)","DOI":"10.1145\/258533.258666"},{"issue":"5","key":"25_CR22","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1145\/585265.585268","volume":"49","author":"J.M. Kleinberg","year":"2002","unstructured":"Kleinberg, J.M., Tardos, \u00c9.: Approximation algorithms for classification problems with pairwise relationships: metric labeling and markov random fields. J. ACM\u00a049(5), 616\u2013639 (2002)","journal-title":"J. ACM"},{"issue":"5","key":"25_CR23","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E. Koutsoupias","year":"1995","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. Jornal of the ACM\u00a042(5), 971\u2013983 (1995)","journal-title":"Jornal of the ACM"},{"issue":"2","key":"25_CR24","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M.S. Manasse","year":"1990","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. Journal of Algorithms\u00a011(2), 208\u2013230 (1990)","journal-title":"Journal of Algorithms"},{"key":"25_CR25","unstructured":"Meyerson, A.: http:\/\/www.cs.ucla.edu\/~awm\/talks\/kserver.ppt"},{"key":"25_CR26","doi-asserted-by":"crossref","unstructured":"Seiden, S.S.: A general decomposition theorem for the k-server problem. In: Proceedings of the 9th Annual European Symposium on Algorithms, pp. 86\u201397 (2001)","DOI":"10.1007\/3-540-44676-1_7"},{"issue":"2","key":"25_CR27","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM\u00a028(2), 202\u2013208 (1985)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T16:31:24Z","timestamp":1740241884000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}