TY - GEN

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

AU - Gupta, Anupam

AU - Kumar, Amit

AU - Panigrahi, Debmalya

N1 - Publisher Copyright:
© 2022 IEEE.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - k server

KW - online algorithms

UR - http://www.scopus.com/inward/record.url?scp=85127193169&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85127193169&partnerID=8YFLogxK

U2 - 10.1109/FOCS52979.2021.00057

DO - 10.1109/FOCS52979.2021.00057

M3 - Conference contribution

AN - SCOPUS:85127193169

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 504

EP - 515

BT - Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021

PB - IEEE Computer Society

T2 - 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021

Y2 - 7 February 2022 through 10 February 2022

ER -