When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1853
URN: urn:nbn:de:0030-drops-18537
URL: http://drops.dagstuhl.de/opus/volltexte/2009/1853/
 Go to the corresponding LIPIcs Volume Portal

### On Approximating Multi-Criteria TSP

 pdf-format:

### 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$.

### BibTeX - Entry

@InProceedings{manthey:LIPIcs:2009:1853,
author =	{Bodo Manthey},
title =	{{On Approximating Multi-Criteria TSP}},
booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
pages =	{637--648},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-09-5},
ISSN =	{1868-8969},
year =	{2009},
volume =	{3},
editor =	{Susanne Albers and Jean-Yves Marion},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/1853},
URN =		{urn:nbn:de:0030-drops-18537},
doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2009.1853},
annote =	{Keywords: Approximation algorithms, Traveling salesman, Multi-criteria optimization}
}


 Keywords: Approximation algorithms, Traveling salesman, Multi-criteria optimization Seminar: 26th International Symposium on Theoretical Aspects of Computer Science Issue Date: 2009 Date of publication: 19.02.2009

DROPS-Home | Fulltext Search | Imprint