On approximating multi-criteria TSP

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

9 Citations (Scopus)
77 Downloads (Pure)

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 languageEnglish
Title of host publicationProceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009
EditorsSusanne Albers, Jean-Yves Marion
PublisherDagstuhl
Pages637-648
Number of pages12
ISBN (Print)978-3-939897-09-5
DOIs
Publication statusPublished - 2009
Event26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 - Freiburg, Germany
Duration: 26 Feb 200928 Feb 2009
Conference number: 26

Publication series

NameLIPIcs–Leibniz International Proceedings in Informatics
PublisherDagstuhl

Conference

Conference26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009
Abbreviated titleSTACS
CountryGermany
CityFreiburg
Period26/02/0928/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.

Cite this