Chasing Convex Bodies with Linear Competitive Ratio
C. J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang · Society for Industrial and Applied Mathematics eBooks · 2019
We study the problem of chasing convex bodies online: given a sequence of convex bodies Kt ⊆ ℝd the algorithm must respond with points xt ϵ Kt in an on-line 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 -competitive for any sequence of length T.