Randomized k-Server on Hierarchical Binary Trees

Adam Meyerson (UCLA)

Metric K-Server is a major problem in the area of online algorithms. We are given a metric space along with a set of K initial server locations, and a sequence of location requests arrives one at a time. As each request arrives, we must move one of our servers to that location. The goal is to minimize the total (or average) distance traveled by servers. This models emergency response, and also has a wide range of applications relating to caching and paging, robot navigation, and reconfigurable computing. In general we cannot compute an optimum solution without foreknowledge of the request sequence, so we will seek an algorithm with good competitive performance (minimizing the worst-case ratio of our total distance traveled to the optimum).

The major result on K-Server is the Work Function Algorithm by Koutsoupias and Papadimitriou, establishing a 2k-1 competitive deterministic algorithm. Slightly improved results (k-competitive) exist for some special cases and a deterministic lower bound of k is also known. However, in many cases it is possible to improve online competitive results using a randomized algorithm. In this talk, I will present a randomized algorithm for K-Server on a special class of metric spaces -- hierarchical binary trees. While this seems a restrictive case, a slight generalization of this result to non-binary hierarchically structured trees would apply to arbitrary finite metrics because of a recent set of results on randomized metric embedding. This talk presents a number of new ideas, including a model of an online problem as a hierarchy of independent online decision makers and an improved algorithm for a special case of the metrical task system problem.

This is joint work with Aaron Cote (UCLA) and Laura Poplawski (Northeastern) and has been accepted to STOC 2008.

Host: Piotr Indyk

(The Algorithms and Complexity Seminar series talks are usually held Thursdays 4:00-5:15pm in 32-G575.)