Chasing Nested Convex Bodies
November 28, 2018 (GHC 6115)

Friedman and Linial [FL 93] introduced the convex body chasing problem to explore the interplay between geometry and competitive ratio in metrical task systems. In convex body chasing, at each time step $t \in \mathbb{N}$, the online algorithm receives a request in the form of a convex body $K_t \subset \mathbb{R}^d$ and must output a point $x_t \in K_t$. The goal is to minimize the total movement between consecutive output points, where the distance is measured in some given norm.

Recently Bansal et al. [BBE+ 17] gave an $6^d(d!)^2$-competitive algorithm for the \emph{nested} version, where each convex body is contained within the previous one. We propose a different strategy which is $O(d \log d)$-competitive algorithm for this nested convex body chasing problem. Our algorithm works for any norm. This result is almost tight, given an $\Omega(d)$ lower bound for the $\ell_{\infty}$ norm~\cite{FL93}.