Michael Sindelar: The Work Function Algorithm for the Online k-Server Problem

The k-server problem is one of the most important problems in the study of online algorithms. The problem involves moving k distinct mobile servers in a metric space to service a series of requests while minimizing total cost. This model provides a general framework that can be used to study many other online problems. Manasse, McGeoch, and Sleator proposed that there exists an algorithm that solves the k-server problem with a competitive ratio of k. Koutsoupias and Papadimitriou demonstrated the best known upper bound of (2k-1) for this open problem using an algorithm based on a work function. Work functions can be used as a general method for constructing online algorithms, providing a trade-off between "greedy" and "retrospective-greedy" algorithms. This talk provides a detailed proof of the competitive ratio of the WFA for the k-server problem.