{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:30Z","timestamp":1740122370851,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,5,9]],"date-time":"2017-05-09T00:00:00Z","timestamp":1494288000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["11271097","61472092"],"award-info":[{"award-number":["11271097","61472092"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Higher Education of Guangdong","award":["2012LYM0105"],"award-info":[{"award-number":["2012LYM0105"]}]},{"name":"Guangdong Province\u2019s Science and Technology Projects","award":["2012A020602065"],"award-info":[{"award-number":["2012A020602065"]}]},{"name":"Guangzhou Science and Technology Plan Project","award":["201605061403261"],"award-info":[{"award-number":["201605061403261"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61302061"],"award-info":[{"award-number":["61302061"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s10878-017-0135-z","type":"journal-article","created":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T21:53:51Z","timestamp":1494280431000},"page":"1133-1146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A primal\u2013dual online algorithm for the k-server problem on weighted HSTs"],"prefix":"10.1007","volume":"34","author":[{"given":"Wenbin","family":"Chen","sequence":"first","affiliation":[]},{"given":"Fufang","family":"Li","sequence":"additional","affiliation":[]},{"given":"Jianxiong","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Ke","family":"Qi","sequence":"additional","affiliation":[]},{"given":"Maobin","family":"Tang","sequence":"additional","affiliation":[]},{"given":"Xiuni","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,9]]},"reference":[{"issue":"1\u20132","key":"135_CR1","doi-asserted-by":"crossref","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 (2000) Competitive analysis of randomized paging algorithms. Theor Comput Sci 234(1\u20132):203\u2013218","journal-title":"Theor Comput Sci"},{"key":"135_CR2","doi-asserted-by":"crossref","unstructured":"Bansal N, Buchbinder N, Madry A, Naor J (2011) A polylogarithmic-competitive algorithm for the $$k$$ k -server problem. In: FOCS 2011, pp 267\u2013276","DOI":"10.1109\/FOCS.2011.63"},{"key":"135_CR3","doi-asserted-by":"crossref","unstructured":"Bansal N, Buchbinder N, Naor JS (2007) 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":"135_CR4","doi-asserted-by":"crossref","unstructured":"Bansal N, Buchbinder N, Naor JS (2010) Metrical task systems and the $$k$$ k -server problem on HSTs. In ICALP\u201910: Proceedings of the 37th international colloquium on automata, languages and programming, 2010, pp 287\u2013298","DOI":"10.1007\/978-3-642-14165-2_25"},{"key":"135_CR5","doi-asserted-by":"crossref","unstructured":"Bansal N, Buchbinder N, Naor JS (2010) Towards the randomized k-server conjecture: a primal-dual approach. In: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, pp 40\u201355, 2010","DOI":"10.1137\/1.9781611973075.5"},{"key":"135_CR6","doi-asserted-by":"crossref","unstructured":"Bartal Y (1996) Probabilistic approximations of metric spaces and its algorithmic applications. In: Proceedings of the 37th annual IEEE symposium on foundations of computer science, pp 184\u2013193, 1996","DOI":"10.1109\/SFCS.1996.548477"},{"key":"135_CR7","doi-asserted-by":"crossref","unstructured":"Bartal Y (1998) On approximating arbitrary metrices by tree metrics. In: Proceedings of the 30th annual ACM symposium on theory of computing, pp 161\u2013168","DOI":"10.1145\/276698.276725"},{"key":"135_CR8","doi-asserted-by":"crossref","unstructured":"Bartal Y, Bollobas B, Mendel M (2001) A ramsy-type theorem for metric spaces and its applications for metrical task systems and related problems. In: Proceedings of the 42nd annual IEEE symposium on foundations of computer science, pp 396\u2013405","DOI":"10.1109\/SFCS.2001.959914"},{"issue":"1","key":"135_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/331605.331606","volume":"47","author":"Y Bartal","year":"2000","unstructured":"Bartal Y, Grove E (2000) The harmonic $$k$$ k -server algorithm is competitive. J ACM 47(1):1\u201315","journal-title":"J ACM"},{"issue":"2\u20133","key":"135_CR10","first-page":"337","volume":"324","author":"Y Bartal","year":"2000","unstructured":"Bartal Y, Koutsoupias E (2000) On the competitive ratio of the work function algorithm for the $$k$$ k -server problem. Theor Comput Sci 324(2\u20133):337\u2013345","journal-title":"Theor Comput Sci"},{"key":"135_CR11","doi-asserted-by":"crossref","unstructured":"Bartal Y, Linial N, Mendel M, Naor A (2003) On metric ramsey-type phenomena. In: Proceedings of the 35th annual ACM symposium on theory of computing, pp 463\u2013472, 2003","DOI":"10.1145\/780542.780610"},{"key":"135_CR12","doi-asserted-by":"crossref","unstructured":"Blum A, Burch C, Kalai A (1999) Finely-competitive paging. In: Proceedings of the 40th annual symposium on foundations of computer science, pp 450\u2013456","DOI":"10.1109\/SFFCS.1999.814617"},{"key":"135_CR13","doi-asserted-by":"crossref","unstructured":"Blum A, Karloff HJ, Rabani Y, Saks ME (1992) A decomposition theorem and bounds for randomized server problems. In: Proceedings of the 31st annual IEEE symposium on foundations of computer science, pp 197\u2013207","DOI":"10.1109\/SFCS.1992.267772"},{"key":"135_CR14","volume-title":"Online computation and competitive analysis","author":"A Borodin","year":"1998","unstructured":"Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge"},{"key":"135_CR15","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Jain K, Naor J (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. In: Proceedings 14th European symposium on algorithms (ESA), pp 253\u2013264, 2007","DOI":"10.1007\/978-3-540-75520-3_24"},{"key":"135_CR16","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Naor J (2005) Online primal-dual algorithms for covering and packing problems. In: Proceedings 12th European symposium on algorithms (ESA), volume 3669 of Lecture notes in computer science, pp 689\u2013701. Springer, 2005","DOI":"10.1007\/11561071_61"},{"key":"135_CR17","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Naor J (2006) Improved bounds for online routing and packing via a primal-dual approach. In: Proceedings 47th symposium foundations of computer science, pp 293\u2013304, 2006","DOI":"10.1109\/FOCS.2006.39"},{"issue":"2\u20133","key":"135_CR18","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder N, Naor J (2009) The design of competitive online algorithms via a primal-dual approach. Found Trends Theor Comput Sci 3(2\u20133):93\u2013263","journal-title":"Found Trends Theor Comput Sci"},{"key":"135_CR19","doi-asserted-by":"crossref","unstructured":"Chiplunkar A, Vishwanathan S (2013) On randomized memoryless algorithms for the weighted K-server problem. In: The IEEE 54th annual symposium on foundations of computer science, pp 11\u201319","DOI":"10.1109\/FOCS.2013.10"},{"issue":"1","key":"135_CR20","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1137\/0220008","volume":"20","author":"M Chrobak","year":"1991","unstructured":"Chrobak M, Larmore L (1991) An optimal on-line algorithm for k-servers on trees. SIAM J Comput 20(1):144\u2013148","journal-title":"SIAM J Comput"},{"key":"135_CR21","doi-asserted-by":"crossref","unstructured":"Cot\u00e9 A, Meyerson A, Poplawski L (2008) Randomized $$k$$ k -server on hierarchical binary trees. In: Proceedings of the 40th annual ACM symposium on theory of computing, pp 227\u2013234","DOI":"10.1145\/1374376.1374411"},{"issue":"1","key":"135_CR22","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1002\/rsa.20124","volume":"29","author":"B Csaba","year":"2006","unstructured":"Csaba B, Lodha S (2006) A randomized on-line algorithm for the $$k$$ k -server problem on a line. Random Struct Algorithms 29(1):82\u2013104","journal-title":"Random Struct Algorithms"},{"key":"135_CR23","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol J, Rao S, Talwar K (2003) A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of the 35th annual ACM symposium on theory of computing, pp 448\u2013455","DOI":"10.1145\/780542.780608"},{"issue":"4","key":"135_CR24","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A Fiat","year":"1991","unstructured":"Fiat A, Karp RM, Luby M, McGeoch LA, Sleator DD, Young NE (1991) Competitive paging algorithms. J Algorithms 12(4):685\u2013699","journal-title":"J Algorithms"},{"issue":"3","key":"135_CR25","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1016\/S0022-0000(05)80060-1","volume":"48","author":"A Fiat","year":"1994","unstructured":"Fiat A, Rabani Y, Ravid Y (1994) Competitive $$k$$ k -server algorithms. J Comput Syst Sci 48(3):410\u2013428","journal-title":"J Comput Syst Sci"},{"key":"135_CR26","doi-asserted-by":"crossref","unstructured":"Grove EF (1991) The harmonic online $$k$$ k -server algorithm is competitive. In: Proceedings of the 23rd annual ACM symposium on theory of computing, pp 260\u2013266","DOI":"10.1145\/103418.103448"},{"issue":"2","key":"135_CR27","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/j.cosrev.2009.04.002","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias E (2009) The $$k$$ k -server problem. Comput Sci Rev 3(2):105\u2013118","journal-title":"Comput Sci Rev"},{"issue":"5","key":"135_CR28","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E Koutsoupias","year":"1995","unstructured":"Koutsoupias E, Papadimitriou CH (1995) On the $$k$$ k -server conjecture. J ACM 42(5):971\u2013983","journal-title":"J ACM"},{"key":"135_CR29","unstructured":"Manasse MS, McGeoch LA, Sleator DD (1988) Competitive algorithms for online problems. In: Proceedings of the 20th annual ACM symposium on theory of computing, pp 322\u2013333"},{"key":"135_CR30","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M Manasse","year":"1990","unstructured":"Manasse M, McGeoch LA, Sleator D (1990) Competitive algorithms for server problems. J Algorithms 11:208\u2013230","journal-title":"J Algorithms"},{"issue":"6","key":"135_CR31","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1007\/BF01759073","volume":"6","author":"LA McGeoch","year":"1991","unstructured":"McGeoch LA, Sleator DD (1991) A strongly competitive randomized paging algorithm. Algorithmica 6(6):816\u2013825","journal-title":"Algorithmica"},{"issue":"1","key":"135_CR32","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00224-012-9434-z","volume":"56","author":"M Renault","year":"2015","unstructured":"Renault M, Ros\u00e9n A (2015) On online algorithms with advice for the k-server problem. Theory Comput Syst 56(1):3\u201321","journal-title":"Theory Comput Syst"},{"issue":"1","key":"135_CR33","first-page":"19","volume":"43","author":"R Sitters","year":"2011","unstructured":"Sitters R (2011) The generalized work function algorithm is competitive for the generalized 2-server problem. Siam J Comput 43(1):19\u201325","journal-title":"Siam J Comput"},{"issue":"2","key":"135_CR34","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator DD, Tarjan RE (1985) Amortized efficiency of list update and paging rules. Commun ACM 28(2):202\u2013208","journal-title":"Commun ACM"},{"key":"135_CR35","unstructured":"T\u00fcrko\u011flu D (2005) The $$k$$ k -server problem and fractional analysis. Master\u2019s Thesis, The University of Chicago. http:\/\/people.cs.uchicago.edu\/duru\/papers\/masters.pdf"},{"issue":"4","key":"135_CR36","doi-asserted-by":"crossref","first-page":"836","DOI":"10.1007\/s10878-013-9621-0","volume":"29","author":"Y Xu","year":"2015","unstructured":"Xu Y, Li H, He C, Luo L (2015) The online k-server problem with max-distance objective. J Combin Optim 29(4):836\u2013846","journal-title":"J Combin Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0135-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0135-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0135-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T19:03:56Z","timestamp":1569265436000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0135-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,9]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["135"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0135-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,5,9]]}}}