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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International