@inproceedings{41da4cdc33f34ffbb7302190651deba4,

title = "Chasing convex bodies with linear competitive ratio",

abstract = "We study the problem of chasing convex bodies online: given a sequence of convex bodies Kt ⊆ Rd the algorithm must respond with points xt ∈ Kt in an online fashion (i.e., xt is chosen before Kt+1 is revealed). The objective is to minimize the total distance between successive points in this sequence. Recently, Bubeck et al. (STOC 2019) gave a 2O(d)-competitive algorithm for this problem. We give an algorithm that is O(min(d, √dlog T))-competitive for any sequence of length T.",

author = "Argue, {C. J.} and Anupam Gupta and Guru Guruganesh and Ziye Tang",

note = "Publisher Copyright: Copyright {\textcopyright} 2020 by SIAM; 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 ; Conference date: 05-01-2020 Through 08-01-2020",

year = "2020",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "1519--1524",

editor = "Shuchi Chawla",

booktitle = "31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020",

}