{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:26Z","timestamp":1740109286740,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T00:00:00Z","timestamp":1576800000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T00:00:00Z","timestamp":1576800000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["617951"],"award-info":[{"award-number":["617951"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.022.211"],"award-info":[{"award-number":["639.022.211"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura Cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["P202\/12\/G061"],"award-info":[{"award-number":["P202\/12\/G061"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00453-019-00661-x","type":"journal-article","created":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T08:04:30Z","timestamp":1576829070000},"page":"1640-1653","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Nested Convex Bodies are Chaseable"],"prefix":"10.1007","volume":"82","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[]},{"given":"Martin","family":"B\u00f6hm","sequence":"additional","affiliation":[]},{"given":"Marek","family":"Eli\u00e1\u0161","sequence":"additional","affiliation":[]},{"given":"Grigorios","family":"Koumoutsos","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6984-4007","authenticated-orcid":false,"given":"Seeun William","family":"Umboh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,12,20]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Andrew, L.H., Barman, S., Ligett, K., Lin, M., Meyerson, A., Roytman, A., Wierman, A.: A tale of two metrics: simultaneous bounds on competitiveness and regret. In: Proceedings of COLT 2013, pp. 741\u2013763 (2013)","key":"661_CR1","DOI":"10.1145\/2465529.2465533"},{"unstructured":"Andrew, L.H., Barman, S., Ligett, K., Lin, M., Meyerson, A., Roytman, A., Wierman, A.: A tale of two metrics: simultaneous bounds on competitiveness and regret. ArXiv e-prints, arXiv:1508.03769 (2015)","key":"661_CR2"},{"doi-asserted-by":"crossref","unstructured":"Antoniadis, A., Barcelo, N., Nugent, M., Pruhs, K., Schewior, K., Scquizzato, M.: Chasing convex bodies and functions.In: Proceedings of LATIN 2016, pp. 68\u201381 (2016)","key":"661_CR3","DOI":"10.1007\/978-3-662-49529-2_6"},{"doi-asserted-by":"crossref","unstructured":"Antoniadis, A., Schewior, K.: A tight lower bound for online convex optimization with switching costs. In: Proceedings of WAOA 2017, pp. 164\u2013175 (2017)","key":"661_CR4","DOI":"10.1007\/978-3-319-89441-6_13"},{"doi-asserted-by":"crossref","unstructured":"Argue, C.J., Bubeck, S., Cohen, M.B., Gupta, A., Lee, Y.T.: A nearly-linear bound for chasing nested convex bodies. In: Proceedings of SODA 2019, pp. 117\u2013122 (2019)","key":"661_CR5","DOI":"10.1137\/1.9781611975482.8"},{"doi-asserted-by":"crossref","unstructured":"Argue, C.J., Gupta, A., Guruganesh, G., Tang, Z.: Chasing convex bodies with linear competitive ratio. ArXiv e-prints, arXiv:1905.11877 (2019)","key":"661_CR6","DOI":"10.1137\/1.9781611975994.93"},{"doi-asserted-by":"crossref","unstructured":"Bansal, N., B\u00f6hm, M., Eli\u00e1\u0161, M., Koumoutsos, G., Umboh, S.W.: Nested convex bodies are chaseable. In: Proceedings of SODA 2018, pp. 1253\u20131260 (2018)","key":"661_CR7","DOI":"10.1137\/1.9781611975031.81"},{"unstructured":"Bansal, N., Gupta, A., Krishnaswamy, R., Pruhs, K., Schewior, K., Stein, C.: A 2-competitive algorithm for online convex optimization with switching costs. In: Proceedings of APPROX\/RANDOM 2015, pp. 96\u2013109 (2015)","key":"661_CR8"},{"issue":"5","key":"661_CR9","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1016\/j.jcss.2005.05.008","volume":"72","author":"Yair Bartal","year":"2006","unstructured":"Bartal, Yair, Bollob\u00e1s, B\u00e9la, Mendel, Manor: Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. Syst. Sci. 72(5), 890\u2013921 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"661_CR10","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.tcs.2004.06.001","volume":"324","author":"Yair Bartal","year":"2004","unstructured":"Bartal, Yair, Koutsoupias, Elias: On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci. 324(2), 337\u2013345 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"661_CR11","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"Allan Borodin","year":"1992","unstructured":"Borodin, Allan, Linial, Nathan, Saks, Michael E.: An optimal on-line algorithm for metrical task system. J. ACM 39(4), 745\u2013763 (1992)","journal-title":"J. ACM"},{"unstructured":"Bubeck, S., Lee, Y. T., Li, Y., Sellke, M.: Chasing nested convex bodies nearly optimally. ArXiv e-prints, arXiv:1811.00999 (2018)","key":"661_CR12"},{"doi-asserted-by":"crossref","unstructured":"Bubeck, S., Lee, Y.T., Li, Y., Sellke, M.: Competitively chasing convex bodies. In: Proceedings of STOC 2019, pp. 861\u2013868 (2019)","key":"661_CR13","DOI":"10.1145\/3313276.3316314"},{"doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Chen, S., Naor, J.: Competitive analysis via regularization. In: Proceedings of SODA 2014, pp. 436\u2013444 (2014)","key":"661_CR14","DOI":"10.1137\/1.9781611973402.32"},{"issue":"2","key":"661_CR15","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"Niv Buchbinder","year":"2009","unstructured":"Buchbinder, Niv, Naor, Joseph: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"661_CR16","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1006\/jagm.1996.0024","volume":"20","author":"William R Burley","year":"1996","unstructured":"Burley, William R.: Traversing layered graphs using the work function algorithm. J. Algorithms 20(3), 479\u2013511 (1996)","journal-title":"J. Algorithms"},{"key":"661_CR17","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/BFb0029565","volume-title":"Online Algorithms: The State of the Art","author":"M Chrobak","year":"1998","unstructured":"Chrobak, M., Larmore, L.L.: Metrical task systems, the server problem and the work function algorithm. In: Fiat, A., Gerhard, J. (eds.) Online Algorithms: The State of the Art, pp. 74\u201396. Springer, Berlin (1998)"},{"doi-asserted-by":"crossref","unstructured":"Fiat, A., Mendel, M.: Better algorithms for unfair metrical task systems and applications. In: Proceedings of STOC 2000, pp. 725\u2013734 (2000)","key":"661_CR18","DOI":"10.1145\/335305.335408"},{"key":"661_CR19","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/BF02189324","volume":"9","author":"Joel Friedman","year":"1993","unstructured":"Friedman, Joel, Linial, Nathan: On convex body chasing. Discrete Comput. Geom. 9, 293\u2013321 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"661_CR20","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"Elias Koutsoupias","year":"1995","unstructured":"Koutsoupias, Elias, Papadimitriou, Christos H.: On the k-server conjecture. J. ACM 42(5), 971\u2013983 (1995)","journal-title":"J. ACM"},{"key":"661_CR21","volume-title":"Understanding and Using Linear Programming","author":"Ji\u0159\u00ed Matou\u0161ek","year":"2007","unstructured":"Matou\u0161ek, Ji\u0159\u00ed, G\u00e4rtner, Bernd: Understanding and Using Linear Programming. Springer, Berlin (2007)"},{"doi-asserted-by":"crossref","unstructured":"Sellke, M.: Chasing convex bodies optimally. ArXiv e-prints, arXiv:1905.11968 (2019)","key":"661_CR22","DOI":"10.1137\/1.9781611975994.92"},{"issue":"1","key":"661_CR23","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/120885309","volume":"43","author":"R Sitters","year":"2014","unstructured":"Sitters, R.: The generalized work function algorithm is competitive for the generalized 2-server problem. SIAM J. Comput. 43(1), 96\u2013125 (2014)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"661_CR24","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1145\/1147954.1147960","volume":"53","author":"RA Sitters","year":"2006","unstructured":"Sitters, R.A., Stougie, L.: The generalized two-server problem. J. ACM 53(3), 437\u2013458 (2006)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00661-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00661-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00661-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,19]],"date-time":"2020-12-19T00:42:48Z","timestamp":1608338568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00661-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,20]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["661"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00661-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,12,20]]},"assertion":[{"value":"21 August 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}