{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:14:51Z","timestamp":1759335291365,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T00:00:00Z","timestamp":1628726400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1907820"],"award-info":[{"award-number":["CCF-1907820"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>\n            We study the problem of chasing convex bodies online: given a sequence of convex bodies\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            the algorithm must respond with points\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            in an online fashion (i.e.,\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            is chosen before\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et\u00a0al. (STOC 2019) gave a\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            -competitive algorithm for this problem. We give an algorithm that is\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            -competitive for any sequence of length\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            .\n          <\/jats:p>","DOI":"10.1145\/3450349","type":"journal-article","created":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T19:06:46Z","timestamp":1628795206000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Chasing Convex Bodies with Linear Competitive Ratio"],"prefix":"10.1145","volume":"68","author":[{"given":"C. J.","family":"Argue","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziye","family":"Tang","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guru","family":"Guruganesh","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,8,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0339-5"},{"volume-title":"Chasing convex bodies and functions","author":"Antoniadis Antonios","key":"e_1_2_1_2_1","unstructured":"Antonios Antoniadis , Neal Barcelo , Michael Nugent , Kirk Pruhs , Kevin Schewior , and Michele Scquizzato . 2016. Chasing convex bodies and functions . In LATIN. Springer , Berlin , 68\u201381. DOI:https:\/\/doi.org\/10.1007\/978-3-662-49529-2_6 10.1007\/978-3-662-49529-2_6 Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Kevin Schewior, and Michele Scquizzato. 2016. Chasing convex bodies and functions. In LATIN. Springer, Berlin, 68\u201381. DOI:https:\/\/doi.org\/10.1007\/978-3-662-49529-2_6"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310443"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175351"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/502969"},{"volume-title":"Geometric Nonlinear Functional Analysis","author":"Benyamini Yoav","key":"e_1_2_1_6_1","unstructured":"Yoav Benyamini and Joram Lindenstrauss . 2000. Geometric Nonlinear Functional Analysis . Vol. 1 . AMS Colloquium Publications, Vol . 48. American Mathematical Society , Providence, RI. xii+488 pages. Yoav Benyamini and Joram Lindenstrauss. 2000. Geometric Nonlinear Functional Analysis. Vol. 1. AMS Colloquium Publications, Vol. 48. American Mathematical Society, Providence, RI. xii+488 pages."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146588"},{"key":"e_1_2_1_8_1","volume-title":"Yuanzhi Li, and Mark Sellke.","author":"Bubeck S\u00e9bastien","year":"2018","unstructured":"S\u00e9bastien Bubeck , Bo\u2019az Klartag , Yin Tat Lee , Yuanzhi Li, and Mark Sellke. 2018 . Chasing nested convex bodies nearly optimally. CoRR abs\/1811.00999 (2018). arXiv:1811.00999. http:\/\/arxiv.org\/abs\/1811.00999. S\u00e9bastien Bubeck, Bo\u2019az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. 2018. Chasing nested convex bodies nearly optimally. CoRR abs\/1811.00999 (2018). arXiv:1811.00999. http:\/\/arxiv.org\/abs\/1811.00999."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316314"},{"key":"e_1_2_1_10_1","unstructured":"Niangjun Chen Gautam Goel and Adam Wierman. 2018. Smoothed online convex optimization in high dimensions via online balanced descent. arXiv:1803.10366.  Niangjun Chen Gautam Goel and Adam Wierman. 2018. Smoothed online convex optimization in high dimensions via online balanced descent. arXiv:1803.10366."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189324"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.03.025"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3454287.3454455"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210128"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jath.1996.0043"},{"key":"e_1_2_1_16_1","volume-title":"Convex Bodies: The Brunn-Minkowski Theory. Encyclopedia of Mathematics and its Applications","author":"Schneider Rolf","year":"2014","unstructured":"Rolf Schneider . 2014 . Convex Bodies: The Brunn-Minkowski Theory. Encyclopedia of Mathematics and its Applications , Vol. 151 . Cambridge University Press , Cambridge . xxii+736 pages. Rolf Schneider. 2014. Convex Bodies: The Brunn-Minkowski Theory. Encyclopedia of Mathematics and its Applications, Vol. 151. Cambridge University Press, Cambridge. xxii+736 pages."},{"key":"e_1_2_1_17_1","volume-title":"Chasing convex bodies optimally. CoRR abs\/1905.11968","author":"Sellke Mark","year":"2019","unstructured":"Mark Sellke . 2019. Chasing convex bodies optimally. CoRR abs\/1905.11968 ( 2019 ). arXiv:1905.11968. http:\/\/arxiv.org\/abs\/1905.11968. Mark Sellke. 2019. Chasing convex bodies optimally. CoRR abs\/1905.11968 (2019). arXiv:1905.11968. http:\/\/arxiv.org\/abs\/1905.11968."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/120885309"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450349","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450349","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:44Z","timestamp":1750191524000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,12]]},"references-count":18,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3450349"],"URL":"https:\/\/doi.org\/10.1145\/3450349","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2021,8,12]]},"assertion":[{"value":"2020-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}