Online service with delay

DOI10.1145/3055399.3055475MaRDI QIDQ4978002zbMATH OpenOpenAlexFDO

Authors Arun Ganesh, Rong Ge, Debmalya Panigrahi, Yossi Azar

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.05611

zbMATH Keywords

\(k\)-servercompetitive ratioonline algorithmspagingweighted paging

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27)

Abstract: 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 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 hope this technique will be useful for related problems such as reordering buffer management, online TSP, vehicle routing, etc. We also generalize our results to $k>1$ servers.

Recommendations

• Online service with delay
• Online service with delay on a line
• Online matching: haste makes waste!
• Online k-Server Routing Problems
• Online k-server routing problems

Cited in

(17)

• Online service with delay on a line
• New results on multi-level aggregation
• On bin packing with clustering and bin packing with delays
• Online service with delay
• Impatient Online Matching
• Caching with time windows and delays
• Online Algorithms for Multilevel Aggregation
• On a Slow Server Problem
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 7651147 (Why is no real title available?)
• The k-Server Problem with Delays on the Uniform Metric Space
• Improved and deterministic online service with deadlines or delay
• List update with delays or time windows
• Online deterministic minimum cost bipartite matching with delays on a line
• Online matching with delays and stochastic arrival times
• Online multi-level aggregation with delays and stochastic arrivals
• Nearly-optimal algorithm for non-clairvoyant service with delay

This page was built for publication: Online service with delay

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978002)