O(d)-competitive Convex Body Chasing
November 13, 2019 (NSH 3305)

We study the problem of chasing convex bodies online: given a sequence of convex bodies K_t ⊆ R^d the algorithm must respond with points x_t ∈ K_t in an online fashion (i.e., x_t is chosen before K_{t+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 2^{O(d)} -competitive algorithm for this problem. We give an algorithm that is O(min(d, √ d log T))-competitive for any sequence of length T.