Skip to main content

Online Service with Delay

Publication ,  Other
Azar, Y; Ganesh, A; Ge, R; Panigrahi, D
Published in: ACM Transactions on Algorithms
August 1, 2021

In this article, we introduce the online service with delay problem. In this problem, there are n points in a metric space that issue service requests over time, and there is a server that serves these requests. The goal is to minimize the sum of distance traveled by the server and the total delay (or a penalty function thereof) in serving the requests. This problem models the fundamental tradeoff between batching requests to improve locality and reducing delay to improve response time, which has many applications in operations management, operating systems, logistics, supply chain management, and scheduling. Our main result is to show a poly-logarithmic competitive ratio for the online service with delay problem. This result is obtained by an algorithm that we call the preemptive service algorithm. The salient feature of this algorithm is a process called preemptive service, which uses a novel combination of (recursive) time forwarding and spatial exploration on a metric space. We also generalize our results to k > 1 servers and obtain stronger results for special metrics such as uniform and star metrics that correspond to (weighted) paging problems.

Duke Scholars

Published In

ACM Transactions on Algorithms

DOI

EISSN

1549-6333

ISSN

1549-6325

Publication Date

August 1, 2021

Volume

17

Issue

3

Related Subject Headings

  • Computation Theory & Mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 4605 Data management and data science
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Azar, Y., Ganesh, A., Ge, R., & Panigrahi, D. (2021). Online Service with Delay. ACM Transactions on Algorithms. https://doi.org/10.1145/3459925
Azar, Y., A. Ganesh, R. Ge, and D. Panigrahi. “Online Service with Delay.” ACM Transactions on Algorithms, August 1, 2021. https://doi.org/10.1145/3459925.
Azar Y, Ganesh A, Ge R, Panigrahi D. Online Service with Delay. Vol. 17, ACM Transactions on Algorithms. 2021.
Azar, Y., et al. “Online Service with Delay.” ACM Transactions on Algorithms, vol. 17, no. 3, 1 Aug. 2021. Scopus, doi:10.1145/3459925.
Azar Y, Ganesh A, Ge R, Panigrahi D. Online Service with Delay. ACM Transactions on Algorithms. 2021.

Published In

ACM Transactions on Algorithms

DOI

EISSN

1549-6333

ISSN

1549-6325

Publication Date

August 1, 2021

Volume

17

Issue

3

Related Subject Headings

  • Computation Theory & Mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 4605 Data management and data science
  • 0802 Computation Theory and Mathematics
  • 0103 Numerical and Computational Mathematics