Algorithms Seminar

Online Service with Delay

Speaker:Arun Ganesh
Date: Thursday, April 13, 2017
Time: 11:30am - 12:30pm
Location: D344 LSRC, Duke


In this project, 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 (or monotone penalty functions of delay). 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.


Arun Ganesh is an undergraduate senior studying computer science at Duke with an interest in theory.