Earliest Deadline First Is a 2-Approximation for DARP with Time Windows
摘要
Dial-a-Ride problems (DARP) require determining a schedule to efficiently serve transportation requests in various scenarios. We consider a variant of offline DARP in a uniform metric space where requests have release times and deadlines, and are all of equal duration and value. The goal is for a single unit-speed, unit-capacity server to serve as many requests as possible by an overall time limit, and this problem is NP-hard. We show that a natural greedy algorithm, Earliest Deadline First, is a 2-approximation, and this is tight.