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

arXiv: https://arxiv.org/abs/2111.09255 · HTML: https://mlsanity.com/paper/2111.09255/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2021.

## Built on by (most cited first, 1 of 1)

- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)

## Abstract (arXiv)

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.