Theory Lunch Seminar

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

 

Event Website:

http://www.cs.cmu.edu/~theorylunch/abstractsHTML/November%2028,%202018.html

For More Information, Contact:

Keywords:

Seminar Series