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:
  https://escholarship.org/uc/item/3dw086dn
• Availability:
  • Find a library where document is available. Order URL: http://www.its.berkeley.edu/publications/
• 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

• Media Type: Digital/other
• Features: Appendices; Figures; References;
• Pagination: 13p
• Serial:
  • Research Report (University of California, Berkeley. Institute of Transportation Studies)

Subject/Index Terms

• TRT Terms: Algorithms; Logistics; Mathematical models; Traveling salesman problem
• Subject Areas: Freight Transportation; Highways; Operations and Traffic Management; Research; I70: Traffic and Transport;

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 28 2007 10:56AM