{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:55Z","timestamp":1759637635505},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,8,20]],"date-time":"2015-08-20T00:00:00Z","timestamp":1440028800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,10]]},"DOI":"10.1007\/s00224-015-9649-x","type":"journal-article","created":{"date-parts":[[2015,8,19]],"date-time":"2015-08-19T05:25:42Z","timestamp":1439961942000},"page":"476-499","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On the Advice Complexity of the k-server Problem Under Sparse Metrics"],"prefix":"10.1007","volume":"59","author":[{"given":"Sushmita","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shahin","family":"Kamali","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,20]]},"reference":[{"key":"9649_CR1","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.tcs.2004.06.001","volume":"324","author":"Y Bartal","year":"2004","unstructured":"Bartal, Y., Koutsoupias, E.: On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci. 324, 337\u2013345 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9649_CR2","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/S0304-3975(01)00252-3","volume":"287","author":"W Bein","year":"2002","unstructured":"Bein, W., Chrobak, M., Larmore, L.L.: The 3-server problem in the plane. Theor. Comput. Sci. 287, 387\u2013391 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"9649_CR3","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1016\/j.tcs.2010.08.022","volume":"412","author":"W Bein","year":"2011","unstructured":"Bein, W., Iwama, K., Kawahara, J., Larmore, L.L., Oravec, J.A.: A randomized algorithm for two servers in cross polytope spaces. Theor. Comput. Sci. 412(7), 563\u2013572 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9649_CR4","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1007\/s00453-013-9819-7","volume":"70","author":"MP Bianchi","year":"2014","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H., Hromkovi\u010d, J., Keller, L.: Online coloring of bipartite graphs with and without advice. Algorithmica 70(1), 92\u2013111 (2014)","journal-title":"Algorithmica"},{"key":"9649_CR5","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.tcs.2014.06.027","volume":"554","author":"MP Bianchi","year":"2014","unstructured":"Bianchi, M.P., B\u00f6ckenhauer, H., Hromkovi\u010d, J., Krug, S., Steffen, B.: On the advice complexity of the online L(2,1)-coloring problem on paths and cycles. Theor. Comput. Sci 554, 22\u201339 (2014)","journal-title":"Theor. Comput. Sci"},{"key":"9649_CR6","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.tcs.2014.01.027","volume":"527","author":"H Bo\u0307ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H., Komm, D., Kr\u00e1lovi\u010d, R., Rossmanith, P.: The online knapsack problem: Advice and randomization. Theor. Comput. Sci. 527, 61\u201372 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9649_CR7","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.tcs.2014.06.006","volume":"554","author":"HJ B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H.J., Hromkovi\u010d, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The string guessing problem as a method to prove lower bounds on the advice complexity. Theor. Comput. Sci. 554, 95\u2013108 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9649_CR8","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: On the advice complexity of the k-server problem. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), LNCS, vol. 6755, pp. 207\u2013218 (2011)","DOI":"10.1007\/978-3-642-22006-7_18"},{"key":"9649_CR9","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the advice complexity of online problems. In: Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), LNCS, vol. 5878, pp. 331\u2013340 (2009)","DOI":"10.1007\/978-3-642-10631-6_35"},{"key":"9649_CR10","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernet. 11, 1\u201323 (1993)","journal-title":"Acta Cybernet."},{"key":"9649_CR11","doi-asserted-by":"crossref","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: On the list update problem with advice. In: Proceedings of the 8th International Conference on Language and Automata Theory (LATA) (2014)","DOI":"10.1007\/978-3-319-04921-2_17"},{"key":"9649_CR12","doi-asserted-by":"crossref","unstructured":"Boyar, J., Kamali, S., Larsen, K.S., L\u00f3pez-Ortiz, A.: Online bin packing with advice. In: Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS) (2014)","DOI":"10.1007\/s00453-014-9955-8"},{"key":"9649_CR13","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1137\/0404017","volume":"4","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Karloff, H., Payne, T.H., Vishwanathan, S.: New results on server problems. SIAM J. Discret. Math. 4, 172\u2013181 (1991)","journal-title":"SIAM J. Discret. Math."},{"key":"9649_CR14","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1137\/0220008","volume":"20","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Larmore, L.L.: An optimal online algorithm for k-servers on trees. SIAM J. Comput. 20, 144\u2013148 (1991)","journal-title":"SIAM J. Comput."},{"key":"9649_CR15","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1145\/174130.174131","volume":"40","author":"D Coppersmith","year":"1993","unstructured":"Coppersmith, D., Doyle, P.G., Raghavan, P., Snir, M.: Random walks on weighted graphs and applications to on-line algorithms. J. ACM 40, 421\u2013453 (1993)","journal-title":"J. ACM"},{"key":"9649_CR16","doi-asserted-by":"crossref","unstructured":"Dobrev, S., Kr\u00e1lovic, R., Markou, E.: Online graph exploration with advice. In: Proceedings of 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), LNCS, vol. 7355, pp. 267\u2013278 (2012)","DOI":"10.1007\/978-3-642-31104-8_23"},{"key":"9649_CR17","doi-asserted-by":"crossref","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Pardubska\u0307, D.: How much information about the future is needed? In: Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), LNCS, vol. 4910, pp. 247\u2013258 (2008)","DOI":"10.1007\/978-3-540-77566-9_21"},{"issue":"2","key":"9649_CR18","doi-asserted-by":"crossref","first-page":"97","DOI":"10.7155\/jgaa.00120","volume":"10","author":"FF Dragan","year":"2006","unstructured":"Dragan, F.F., Yan, C., Corneil, D.G.: Collective tree spanners and routing in at-free related graphs. J. Graph Algorithm. Appl. 10(2), 97\u2013122 (2006)","journal-title":"J. Graph Algorithm. Appl."},{"issue":"1","key":"9649_CR19","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1137\/S089548010444167X","volume":"20","author":"FF Dragan","year":"2006","unstructured":"Dragan, F.F., Yan, C., Lomonosov, I.: Collective tree spanners of graphs. SIAM J. Discret. Math. 20(1), 241\u2013260 (2006)","journal-title":"SIAM J. Discret. Math."},{"issue":"24","key":"9649_CR20","doi-asserted-by":"crossref","first-page":"2642","DOI":"10.1016\/j.tcs.2010.08.007","volume":"412","author":"Y Emek","year":"2011","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: Online computation with advice. Theor. Comput. Sci. 412(24), 2642\u20132656 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9649_CR21","doi-asserted-by":"crossref","unstructured":"Farzan, A., Kamali, S.: Compact navigation and distance oracles for graphs with small treewidth. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), LNCS, vol. 6755, pp. 268\u2013280 (2011)","DOI":"10.1007\/978-3-642-22006-7_23"},{"key":"9649_CR22","doi-asserted-by":"crossref","unstructured":"Fori\u0161ek, M., Keller, L., Steinov\u00e1, M.: Advice complexity of online coloring for paths. In: Proceedings of the 6th International Conference on Language and Automata Theory (LATA), LNCS, vol. 7183, pp. 228\u2013239 (2012)","DOI":"10.1007\/978-3-642-28332-1_20"},{"issue":"2","key":"9649_CR23","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1137\/S0097539702409927","volume":"34","author":"A Gupta","year":"2004","unstructured":"Gupta, A., Kumar, A., Rastogi, R.: Traveling with a pez dispenser (or, routing issues in mpls). SIAM J. Comput. 34(2), 453\u2013474 (2004)","journal-title":"SIAM J. Comput."},{"key":"9649_CR24","doi-asserted-by":"crossref","unstructured":"Gupta, S., Kamali, S., L\u00f3pez-Ortiz, A.: On advice complexity of the k-server problem under sparse metrics. In: Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO). LNCS (2013)","DOI":"10.1007\/978-3-319-03578-9_5"},{"issue":"1-2","key":"9649_CR25","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF01917434","volume":"8","author":"R Halin","year":"1976","unstructured":"Halin, R.: S-functions for graphs. J. Geom. 8(1-2), 171\u2013186 (1976)","journal-title":"J. Geom."},{"key":"9649_CR26","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Information complexity of online problems. In: Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS, vol. 6281, pp. 24\u201336 (2010)","DOI":"10.1007\/978-3-642-15155-2_3"},{"key":"9649_CR27","unstructured":"Karlin, A., Manasse, M., McGeoch, L., Owicki, S.: Randomized competitive algorithms for non-uniform problems. In: Proceedings of the 1st ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 301\u2013309 (1990)"},{"key":"9649_CR28","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1007\/BF01189993","volume":"11","author":"A Karlin","year":"1994","unstructured":"Karlin, A., Manasse, M., McGeoch, L., Owicki, S.: Competitive randomized algorithms for nonuniform problems. Algorithmica 11, 542\u2013571 (1994)","journal-title":"Algorithmica"},{"key":"9649_CR29","doi-asserted-by":"crossref","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R.: Advice complexity and barely random algorithms. In: Proceedings of the 37th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), LNCS, vol. 6543, pp. 332\u2013343 (2011)","DOI":"10.1007\/978-3-642-18381-2_28"},{"key":"9649_CR30","doi-asserted-by":"crossref","unstructured":"Komm, D., Kr\u00e1lovic, R., M\u00f6mke, T.: On the advice complexity of the set cover problem. In: Proceedings of the 7th International Computer Science Symposium in Russia (CSR), LNCS, vol. 7353, pp. 241\u2013252 (2012)","DOI":"10.1007\/978-3-642-30642-6_23"},{"key":"9649_CR31","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E Koutsoupias","year":"1995","unstructured":"Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. J. ACM 42, 971\u2013983 (1995)","journal-title":"J. ACM"},{"key":"9649_CR32","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(96)00010-5","volume":"57","author":"E Koutsoupias","year":"1996","unstructured":"Koutsoupias, E., Papadimitriou, C.: The 2-evader problem. Inf. Process. Lett. 57, 249\u2013252 (1996)","journal-title":"Inf. Process. Lett."},{"key":"9649_CR33","doi-asserted-by":"crossref","unstructured":"Manasse, M.S., McGeoch, L., Sleator, D.D.: Competitive algorithms for on-line problems. In: Proceedings of the 20th ACM Symposium on Theory of Computing (STOC), pp. 322\u2013333 (1988)","DOI":"10.1145\/62212.62243"},{"issue":"2","key":"9649_CR34","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"MS Manasse","year":"1990","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithm. 11(2), 208\u2013230 (1990)","journal-title":"J. Algorithm."},{"key":"9649_CR35","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF02785579","volume":"114","author":"J Matousek","year":"1999","unstructured":"Matousek, J.: On embedding trees into uniformly convex banach spaces. Israel J. Math. 114, 221\u2013237 (1999)","journal-title":"Israel J. Math."},{"key":"9649_CR36","doi-asserted-by":"crossref","unstructured":"Renault, M.P., Ros\u00e9n, A.: On online algorithms with advice for the k-server problem. In: Proceedings of the 9th Workshop on Approximation and Online Algorithms (WAOA), LNCS, vol. 7164, pp. 198\u2013210 (2011)","DOI":"10.1007\/978-3-642-29116-6_17"},{"issue":"1","key":"9649_CR37","first-page":"49","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. iii. planar tree-width. Journal of Combinatorial Theory. Ser. B 36(1), 49\u201364 (1984)","journal-title":"Ser. B"},{"key":"9649_CR38","doi-asserted-by":"crossref","unstructured":"Seibert, S., Sprock, A., Unger, W.: Advice complexity of the online coloring problem. In: Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC), LNCS, vol. 7878, pp. 345\u2013357 (2013)","DOI":"10.1007\/978-3-642-38233-8_29"},{"issue":"7","key":"9649_CR39","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/j.comgeo.2012.01.015","volume":"45","author":"C Yan","year":"2012","unstructured":"Yan, C., Xiang, Y., Dragan, F.F.: Compact and low delay routing labeling scheme for unit disk graphs. Comput. Geom. 45(7), 305\u2013325 (2012)","journal-title":"Comput. Geom."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9649-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9649-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9649-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T15:14:06Z","timestamp":1567091646000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9649-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,20]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["9649"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9649-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,20]]}}}