Improved and Deterministic Online Service with Deadlines or Delay
Noam Touitou · 2023
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(log2 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.