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 polylog(n, Δ), where Δ is the aspect ratio of the metric space. Prior to our work, the best competitive ratio known for this problem was O(k 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 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.