BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

k-server via multi-scale entropic regulariziation Lee, James


The k-server problem is one of the most well-known and widely studied problems in online algorithms. We present an O(log k)^2-competitive randomized algorithm for the k-server problem on HSTs. A breakthrough of Bansal, Buchbinder, Madry, and Naor gave a poly(log k, log N)-competitive algorithm for HSTs of size N, but no o(k)-competitive algorithm that doesn't depend on N was known. Using this, we obtain a poly(log k, log D)-competitive algorithm for any metric space X, where D is the ratio of the largest to smallest distance in X. Our approach is an instantiation of online mirror descent where the mirror map is a multi-scale entropy. Joint work with Sebastien Bubeck, Michael Cohen, Yin Tat Lee, and Aleksander Madry.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International