# On approximating multi-criteria TSP

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

## Abstract

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$.
Original language English Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 Susanne Albers, Jean-Yves Marion Dagstuhl 637-648 12 978-3-939897-09-5 https://doi.org/10.4230/LIPIcs.STACS.2009.1853 Published - 2009 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 - Freiburg, GermanyDuration: 26 Feb 2009 → 28 Feb 2009Conference number: 26

### Publication series

Name LIPIcs–Leibniz International Proceedings in Informatics Dagstuhl

### Conference

Conference 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 STACS Germany Freiburg 26/02/09 → 28/02/09

## Keywords

• TSP
• Multi-objective optimization
• Multi-criteria optimization
• Approximation algorithms
• Traveling Salesman Problem

## Fingerprint

Dive into the research topics of 'On approximating multi-criteria TSP'. Together they form a unique fingerprint.