Approximation algorithms for deadline-TSP and vehicle routing with time-windows

N. Bansal, A. Blum, S. Chawla, A. Meyerson

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    168 Citations (Scopus)
    1 Downloads (Pure)

    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 languageEnglish
    Title of host publicationProceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC'04, Chicago IL, USA, June 13-15, 2004)
    EditorsL. Babai
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery, Inc
    Pages166-174
    ISBN (Print)1-58113-852-0
    Publication statusPublished - 2004

    Fingerprint

    Dive into the research topics of 'Approximation algorithms for deadline-TSP and vehicle routing with time-windows'. Together they form a unique fingerprint.

    Cite this