%0 Journal Article %1 argue2019chasing %A Argue, C. J. %A Gupta, Anupam %A Guruganesh, Guru %A Tang, Ziye %D 2019 %K convex optimization theory %T Chasing Convex Bodies with Linear Competitive Ratio %U http://arxiv.org/abs/1905.11877 %X We study the problem of chasing convex bodies online: given a sequence of convex bodies $K_tR^d$ the algorithm must respond with points $x_tK_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 T))$-competitive for any sequence of length $T$.

@article{argue2019chasing, abstract = {We study the problem of chasing convex bodies online: given a sequence of convex bodies $K_t\subseteq \mathbb{R}^d$ the algorithm must respond with points $x_t\in 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, \sqrt{d \log T}))$-competitive for any sequence of length $T$.}, added-at = {2019-05-29T19:29:41.000+0200}, author = {Argue, C. J. and Gupta, Anupam and Guruganesh, Guru and Tang, Ziye}, biburl = {https://www.bibsonomy.org/bibtex/218447bd483684372803aa7964f0de4fd/kirk86}, description = {[1905.11877] Chasing Convex Bodies with Linear Competitive Ratio}, interhash = {a7313229cb2f0f06889f72131f134126}, intrahash = {18447bd483684372803aa7964f0de4fd}, keywords = {convex optimization theory}, note = {cite arxiv:1905.11877}, timestamp = {2019-05-29T19:29:41.000+0200}, title = {Chasing Convex Bodies with Linear Competitive Ratio}, url = {http://arxiv.org/abs/1905.11877}, year = 2019 }