Skip to Main content Skip to Navigation
Conference papers

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$.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00360080
Contributor : Publications Loria <>
Submitted on : Tuesday, February 10, 2009 - 5:24:38 PM
Last modification on : Tuesday, October 31, 2017 - 2:22:18 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 10:10:09 PM

File

53-manthey.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00360080, version 1

Collections

Citation

Bodo Manthey. On Approximating Multi-Criteria TSP. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. pp.637-648. ⟨inria-00360080⟩

Share

Metrics

Record views

206

Files downloads

472