Online Service with Delay
||Thursday, April 13, 2017
||11:30am - 12:30pm
||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.