On Approximating Multi-Criteria TSP

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 (\maxtsp). For multi-criteria \maxstsp, where the edge weights have to be symmetric, we devise an algorithm that achieves an approximation ratio of $2/3 - \eps$. For multi-criteria \maxatsp, where the edge weights may be asymmetric, we present an algorithm with an approximation ratio of $1/2 - \eps$. 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 \maxstsp\ 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 (\minatsp). This algorithm achieves a ratio of $\log n + \eps$. 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) + \eps$.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.637-648, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00360080
Contributeur : Publications Loria <>
Soumis le : mardi 10 février 2009 - 17:24:38
Dernière modification le : mardi 31 octobre 2017 - 14:22:18
Document(s) archivé(s) le : mardi 8 juin 2010 - 22:10:09

Fichier

53-manthey.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00360080, version 1

Collections

Citation

Bodo Manthey. On Approximating Multi-Criteria TSP. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.637-648, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00360080〉

Partager

Métriques

Consultations de la notice

83

Téléchargements de fichiers

143