License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.33
URN: urn:nbn:de:0030-drops-122805
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12280/
Go to the corresponding LIPIcs Volume Portal

Rathinam, S. ; Ravi, R. ; Bae, J. ; Sundar, K.

Primal-Dual 2-Approximation Algorithm for the Monotonic Multiple Depot Heterogeneous Traveling Salesman Problem

pdf-format:
LIPIcs-SWAT-2020-33.pdf (0.8 MB)

Abstract

We study a Multiple Depot Heterogeneous Traveling Salesman Problem (MDHTSP) where the cost of the traveling between any two targets depends on the type of the vehicle. The travel costs are assumed to be symmetric, satisfy the triangle inequality, and are monotonic, i.e., the travel costs between any two targets monotonically increases with the index of the vehicles. Exploiting the monotonic structure of the travel costs, we present a 2-approximation algorithm based on the primal-dual method.

BibTeX - Entry

@InProceedings{rathinam_et_al:LIPIcs:2020:12280,
  author =	{S. Rathinam and R. Ravi and J. Bae and K. Sundar},
  title =	{{Primal-Dual 2-Approximation Algorithm for the Monotonic Multiple Depot Heterogeneous Traveling Salesman Problem}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{33:1--33:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Susanne Albers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12280},
  URN =		{urn:nbn:de:0030-drops-122805},
  doi =		{10.4230/LIPIcs.SWAT.2020.33},
  annote =	{Keywords: Approximation Algorithm, Heterogeneous Traveling Salesman Problem, Primal-dual Method}
}

Keywords: Approximation Algorithm, Heterogeneous Traveling Salesman Problem, Primal-dual Method
Collection: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI