Theory Lunch Seminar

Wednesday, November 13, 2019 - 12:00pm to 1:00pm

Location:

3305 Newell-Simon Hall

Speaker:

C.J. ARGUE, Ph.D. Student (Algorithms, Combinatorics and Optimization) http://www.math.cmu.edu/~cargue/

O(d)-competitive Convex Body Chasing

We study the problem of chasing convex bodies online: given a sequence of convex bodies K_t ⊆ R^d the algorithm must respond with points x_t ∈ K_t in an online fashion (i.e., x_t is chosen before K_{t+1} is revealed). The objective is to minimize the total distance between successive points in this sequence. Recently, Bubeck et al. (STOC 2019) gave a 2^{O(d)} -competitive algorithm for this problem. We give an algorithm that is O(min(d, √ d log T))-competitive for any sequence of length T.

Theory YouTube Channel

Event Website:

http://www.cs.cmu.edu/~theorylunch/abstractsHTML/20191113.html

For More Information, Contact:

Keywords:

Seminar Series