2026-08-17T10:22:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12280 2024-03-06T10:49:31Z ddc:004 open_access

Primal-Dual 2-Approximation Algorithm for the Monotonic Multiple Depot Heterogeneous Traveling Salesman Problem Rathinam, S. Ravi, R. Bae, J. Sundar, K. Approximation Algorithm Heterogeneous Traveling Salesman Problem Primal-dual Method 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik S. Rathinam and R. Ravi and J. Bae and K. Sundar 2020 Is Part Of LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2020.33 urn:nbn:de:0030-drops-122805 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.33 eng https://creativecommons.org/licenses/by/3.0/legalcode