A 3/2-approximation algorithm for multiple depot multiple traveling salesman problem (extended abstract)

Zhou Xu, Brian Rodrigues

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

7 Citations (Scopus)

Abstract

As an important extension of the classical traveling salesman problem (TSP), the multiple depot multiple traveling salesman problem (MDMTSP) is to minimize the total length of a collection of tours for multiple vehicles to serve all the customers, where each vehicle must start or stay at its distinct depot. Due to the gap between the existing best approximation ratios for the TSP and for the MDMTSP in literature, which are 3/2 and 2, respectively, it is an open question whether or not a 3/2-approximation algorithm exists for the MDMTSP. We have partially addressed this question by developing a 3/2-approximation algorithm, which runs in polynomial time when the number of depots is a constant.
Original languageEnglish
Title of host publicationAlgorithm Theory - SWAT 2010 - 12th Scandinavian Symposium and Workshops on Algorithm Theory, Proceedings
Pages127-138
Number of pages12
DOIs
Publication statusPublished - 21 Jul 2010
Event12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010 - Bergen, Norway
Duration: 21 Jun 201023 Jun 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6139 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010
CountryNorway
CityBergen
Period21/06/1023/06/10

Keywords

  • Approximation algorithm
  • multiple depots
  • vehicle routing

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this