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$v_{i}$of an$n$-point metric space at time$b_{i}$and comes with a deadline$e_{i}$. One of the$k$servers must be moved to$v_{i}$at some time in the interval [$b_{i}, e_{i}$] to satisfy this request. We give an online algorithm for this problem with a competitive ratio of$\text{poly}\log(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\ \text{poly}\log(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 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.