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

### Location:

ASA Conference Room 6115 Gates Hillman Centers### Speaker:

C.J. ARGUE, Ph.D. Student, Program in Algorithms, Combinatorics and Optimization http://www.math.cmu.edu/~cargue/### 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}.