A Hitting Set Relaxation for k-Server and an Extension to Time-Windows

We study the k-server problem with time-windows. In this problem, each request i arrives at some point vi of an n-point metric space at time bi and comes with a deadline ei. One of the k servers must be moved to vi at some time in the interval [bi, ei] to satisfy this request. We give an online algorithm for this problem with a competitive ratio of rm polylog (n,Delta), where Delta is the aspect ratio of the metric space. Prior to our work, the best competitive ratio known for this problem was O(k · rm polylog(n)) given by Azar et al. (STOC 2017). Our algorithm is based on a new covering linear program relaxation for k-server on HSTs. This LP naturally corresponds to the min-cost flow formulation of k-server, and easily extends to the case of time-windows. We give an online algorithm for obtaining a feasible fractional solution for this LP, and a primal dual analysis framework for accounting the cost of the solution. Together, they yield a new k-server algorithm with poly-logarithmic competitive ratio, and extend to the time-windows case as well. Our principal technical contribution lies in thinking of the covering LP as yielding a em truncated covering LP at each internal node of the tree, which allows us to keep account of server movements across subtrees. We hope that this LP relaxation and the algorithm/analysis will be a useful tool for addressing k-server and related problems.