TIME: 1:30-2:20 pm,  April 15, 2008

PLACE: CSE 503  

SPEAKER: Adam Meyerson
         UCLA

TITLE:Randomized K-Server on Hierarchical Binary Trees


ABSTRACT:

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.