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

Anupam Gupta, Amit Kumar, Debmalya Panigrahi

Browse the full FOCS paper archive.