On approximating multi-criteria TSP

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)


We present approximation algorithms for almost all variants of the multicriteria traveling salesman problem (TSP). First, we devise randomized approximation algorithms for multicriteria maximum traveling salesman problems (Max-TSP). For multicriteria Max-STSP where the edge weights have to be symmetric, we devise an algorithm with an approximation ratio of 2/3 $-\varepsilon.$ For multicriteria Max-ATSP where the edge weights may be asymmetric, we present an algorithm with a ratio of 1/2 $-\varepsilon.$ Our algorithms work for any fixed number k of objectives. Furthermore, we present a deterministic algorithm for bicriteria Max-STSP that achieves an approximation ratio of 7/27. Finally, we present a randomized approximation algorithm for the asymmetric multicriteria minimum TSP with triangle inequality (Min-ATSP). This algorithm achieves a ratio of log $n + \varepsilon.$
Original languageUndefined
Article number17
Pages (from-to)17:1-17:18
Number of pages18
JournalACM transactions on algorithms
Issue number2
Publication statusPublished - Apr 2012


  • EWI-20668
  • Approximation algorithms
  • Multi-objective optimization
  • IR-80244
  • Pareto curves
  • METIS-289629
  • Traveling Salesman Problem

Cite this