Abstract
Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible by their deadlines. We also consider the more general Vehicle Routing with Time-Windows problem, in which each node v also has a release-time R(v) and the goal is to visit as many nodes as possible within their "time-windows" [R(v),D(v)]. No good approximations were known previously for these problems on general metric spaces. We give an O(logn) approximation algorithm for Deadline-TSP, and extend this algorithm to an O(log2n) approximation for the Time-Window problem. We also give a bicriteria approximation algorithm for both problems: Given an e>0, our algorithm produces a (1/e) approximation, while exceeding the deadlines by a factor of 1+e. We use as a subroutine for these results a constant-factor approximation that we develop for a generalization of the orienteering problem in which both the start and the end nodes of the path are fixed. In the process, we give a 3-approximation to the orienteering problem, improving on the previously best known 4-approximation of [6].
Original language | English |
---|---|
Title of host publication | Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC'04, Chicago IL, USA, June 13-15, 2004) |
Editors | L. Babai |
Place of Publication | New York |
Publisher | Association for Computing Machinery, Inc |
Pages | 166-174 |
ISBN (Print) | 1-58113-852-0 |
Publication status | Published - 2004 |