Complexity seminar

Nested Convex Bodies are Chaseable

In the Convex Body Chasing problem, we are given an initial point v in R^d and an online
sequence of n convex bodies F_1,...,F_n. When we receive F_i, we are required to move inside
F_i. Our goal is to minimize the total distance travelled. This fundamental online problem was
first studied by Friedman and Linial (DCG 1993). They proved an Omega(sqrt(d)) lower bound on
the competitive ratio, and conjectured that a competitive ratio depending only on d is possible.
However, despite much interest in the problem, the conjecture remains wide open.

In this work, we give a simple f(d)-competitive algorithm for chasing *nested* convex bodies in
R^d, i.e. when F_2 lies inside F_1, F_3 lies inside F_2 and so on. Among other consequences,
this indicates that the problem is considerably more difficult when the optimal path visits
several points, as opposed to just moving to a single globally feasible position.

Joint work with Nikhil Bansal, Marek Eliáš, Grigorios Koumoutsos, and Seeun William Umboh.