Theory Lunch Seminar

Wednesday, November 28, 2018 - 12:00pm to 1:00pm


ASA Conference Room 6115 Gates Hillman Centers


C.J. ARGUE, Ph.D. Student, Program in Algorithms, Combinatorics and Optimization

Chasing Nested Convex Bodies

Speaker: C. J. Argue

Location: GHC 6115

Chasing Nested Convex Bodies

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 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}.


Event Website:,%202018.html

For More Information, Contact:


Seminar Series