On approximating multi-criteria TSP

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)

Abstract

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
Volume8
Issue number2
DOIs
Publication statusPublished - Apr 2012

Keywords

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

Cite this