Chasing Convex Bodies with Linear Competitive Ratio
share
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((d, √(d T)))-competitive for any sequence of length T.
READ FULL TEXT