Chasing Convex Bodies with Linear Competitive Ratio

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 sum of distances...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-01
Main Authors: Argue, C J, Gupta, Anupam, Guru Guruganesh, Tang, Ziye
Format: Article
Language:English
Subjects:
Algorithms
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 sum of distances between successive points in this sequence. 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\).
ISSN:2331-8422