2026-07-23T21:03:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1853 2024-03-06T10:33:14Z ddc:004 open_access

On Approximating Multi-Criteria TSP Manthey, Bodo Approximation algorithms Traveling salesman Multi-criteria optimization We present approximation algorithms for almost all variants of the multi-criteria traveling salesman problem (TSP), whose performances are independent of the number $k$ of criteria and come close to the approximation ratios obtained for TSP with a single objective function. We present randomized approximation algorithms for multi-criteria maximum traveling salesman problems (Max-TSP). For multi-criteria Max-STSP, where the edge weights have to be symmetric, we devise an algorithm that achieves an approximation ratio of $2/3 - \varepsilon$. For multi-criteria Max-ATSP, where the edge weights may be asymmetric, we present an algorithm with an approximation ratio of $1/2 - \varepsilon$. Our algorithms work for any fixed number $k$ of objectives. To get these ratios, we introduce a decomposition technique for cycle covers. These decompositions are optimal in the sense that no decomposition can always yield more than a fraction of $2/3$ and $1/2$, respectively, of the weight of a cycle cover. Furthermore, we present a deterministic algorithm for bi-criteria Max-STSP\ that achieves an approximation ratio of $61/243 \approx 1/4$. Finally, we present a randomized approximation algorithm for the asymmetric multi-criteria minimum TSP with triangle inequality (Min-ATSP). This algorithm achieves a ratio of $\log n + \varepsilon$. For this variant of multi-criteria TSP, this is the first approximation algorithm we are aware of. If the distances fulfil the $\gamma$-triangle inequality, its ratio is $1/(1-\gamma) + \varepsilon$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bodo Manthey 2009 Is Part Of LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2009.1853 urn:nbn:de:0030-drops-18537 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1853 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode