5/3 - Approximation Algorithm for a Multiple Depot, Terminal Hamiltonian Path Problem

This paper addresses one variant of the Multiple Depot Terminal Hamiltonian Path Problem (MDTHPP). There are no algorithms available in the literature for any multiple depot variant of the Traveling Salesman Problem (TSP) or Hamiltonian Path Problem (HPP) that has an approximation ratio that is better than 2. This paper presents an algorithm with an approximation ratio of 5/3 for MDTHPP, if and when the costs are symmetric and they satisfy triangle inequality.

  • Record URL:
  • Availability:
  • Corporate Authors:

    University of California, Berkeley

    Department of Civil and Environmental Engineering
    Davis Hall
    Berkeley, CA  United States  94720-1710

    University of California, Berkeley

    Institute of Transportation Studies
    McLaughlin Hall
    Berkeley, CA  United States  94720

    California Department of Transportation

    Office of Research, P.O. Box 942873
    Sacramento, CA  United States  94273-0001
  • Authors:
    • Rathinam, S
    • Sengupta, Raja
  • Publication Date: 2007-5

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01055886
  • Record Type: Publication
  • Source Agency: UC Berkeley Transportation Library
  • Report/Paper Numbers: UCB-ITS-RR-2007-1
  • Files: CALTRANS, TRIS, ATRI, STATEDOT
  • Created Date: Aug 2 2007 7:33PM