Approximation algorithms for multi-criteria traveling salesman problems

Bodo Manthey, L. Shankar Ram

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)

Abstract

We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with $\gamma$-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of $\min\left\{1+\gamma,{2\gamma^2\over 2\gamma^2-2\gamma +1}\right\} + \varepsilon$ and a randomized approximation algorithm that achieves a ratio of ${2\gamma^3 + 2\gamma^2\over 3\gamma^2-2\gamma +1} + \varepsilon$. In particular, we obtain a $2+\varepsilon$ approximation for multi-criteria metric STSP. Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with $\gamma$-triangle inequality ratio ${1\gamma\over 1+3\gamma-4\gamma^2}+ \varepsilon$ ), asymmetric TSP (ATSP) with $\gamma$-triangle inequality (ratio ${1\over 2} + {\gamma^3\over 1-3\gamma^2}+ \varepsilon$ ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2).
Original languageUndefined
Article number10.1007/s00453-007-9011-z
Pages (from-to)69-88
Number of pages20
JournalAlgorithmica
Volume53
Issue number1
DOIs
Publication statusPublished - Jan 2009

Keywords

  • EWI-16093
  • IR-68059
  • METIS-264039

Cite this