Faculty Recruiting Make a Gift

The k-Server Problem

11 Dec
Tuesday, 12/11/2018 4:00pm to 5:00pm
Computer Science Building, Room 140
Theory Seminar
Speaker: Lyle McGeoch

There has been extensive research over the last thirty years exploring the power and limitations of on-line algorithms. One part of this work has focused on competitive algorithms, those that are guaranteed to have performance that is within a constant factor of the off-line optimal.

The k-server problem involves scheduling the motion of k servers in a metrical space. Optimally competitive algorithms are known for special cases, and a strong lower bound on the competitive ratio is known for the general problem. A central question remains open: is there an on-line algorithm for the general k-server problem that is k-competitive, matching the lower bound? Most researchers believe that the answer is yes and that the work function algorithm (WFA) achieves this competitive factor.

This talk will explore the k-server problem, the known results, and recent efforts to show that WFA is k-competitive.

Faculty Host
: