Competitive Algorithms for Generalized k-Server

The k-server problem is one of the most natural and fundamental online problems and its study has been quite influential in the development of competitive analysis. Despite various remarkable developments, several natural variants and generalizations of the k-server problem are very poorly understood. In particular, they exhibit very different and intriguing behavior and the techniques for the standard k-server problem do not apply to them. Getting a better understanding of such problems is a natural step towards building a deeper theory of online computation.

In this talk, I will discuss some recent results on generalizations of the k-server problem, in particular:

i) the weighted k-server problem, in which servers have different weights;
ii) the generalized k-server problem, where each server lies in its own metric space; and (if time allows)
iii) the resource augmentation version (the (h,k)-s