A Hitting Set Relaxation for k-Server and an Extension to Time-Windows
share
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 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.
READ FULL TEXT