Chasing convex bodies with linear competitive ratio (invited paper)

Citations Over Time

Abstract

The problem of chasing convex functions is easy to state: faced with a sequence of convex functions f t over d-dimensional Euclidean spaces, the goal of the algorithm is to output a point x t at each time, so that the sum of the function costs f t (x t ), plus the movement costs ||x t − x t − 1 || is minimized. This problem generalizes questions in online algorithms such as caching and the k-server problem. In 1994, Friedman and Linial posed the question of getting an algorithm with a competitive ratio that depends only on the dimension d. In this talk we give an O (d)-competitive algorithm, based on the notion of the Steiner point of a convex body.

Related Papers

• → Tight Bounds for Online TSP on the Line(2020)13 cited
• → A New Approach to Online Scheduling(2016)10 cited
• → Tight Bounds for Online TSP on the Line(2017)5 cited
• A New Approach to Competitive Analysis: Approximating the Optimal Competitive Ratio(2012)