Online service with delay

Conference Paper

In this paper, 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 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, that 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.

Full Text

Duke Authors

Cited Authors

  • Azar, Y; Ganesh, A; Ge, R; Panigrahi, D

Published Date

  • June 19, 2017

Published In

Volume / Issue

  • Part F128415 /

Start / End Page

  • 551 - 563

International Standard Serial Number (ISSN)

  • 0737-8017

International Standard Book Number 13 (ISBN-13)

  • 9781450345286

Digital Object Identifier (DOI)

  • 10.1145/3055399.3055475

Citation Source

  • Scopus