Improved and Deterministic Online Service with Deadlines or Delay

06/09/2023
by   Noam Touitou, et al.
0

We consider the problem of online service with delay on a general metric space, first presented by Azar, Ganesh, Ge and Panigrahi (STOC 2017). The best known randomized algorithm for this problem, by Azar and Touitou (FOCS 2019), is O(log^2 n)-competitive, where n is the number of points in the metric space. This is also the best known result for the special case of online service with deadlines, which is of independent interest. In this paper, we present O(log n)-competitive deterministic algorithms for online service with deadlines or delay, improving upon the results from FOCS 2019. Furthermore, our algorithms are the first deterministic algorithms for online service with deadlines or delay which apply to general metric spaces and have sub-polynomial competitiveness.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset