Approximation algorithms for multi-criteria traveling salesman problems

Bodo Manthey, L. Shankar Ram

Research output: Contribution to journalArticleAcademicpeer-review

13 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 γ-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of min{1+γ,2γ2/2γ2−2γ+1}+ε and a randomized approximation algorithm that achieves a ratio of 2γ3+2γ2/3γ2−2γ+1+ε. In particular, we obtain a 2+ε 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 γ-triangle inequality (ratio 1+γ/1+3γ−4γ2+ε), asymmetric TSP (ATSP) with γ-triangle inequality (ratio 1/2+γ3/1−3γ2+ε ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2).
Original languageEnglish
Pages (from-to)69-88
Number of pages20
JournalAlgorithmica
Volume53
Issue number1
DOIs
Publication statusPublished - Jan 2009

Keywords

  • Approximation algorithms
  • Multi-criteria optimization
  • Traveling salesman problem

Fingerprint

Dive into the research topics of 'Approximation algorithms for multi-criteria traveling salesman problems'. Together they form a unique fingerprint.
  • Approximation algorithms for multi-criteria traveling salesman problems

    Manthey, B. & Ram, L. S., 1 Dec 2007, Approximation and Online Algorithms: 4th International Workshop, WAOA 2006, Revised Papers. Erlebach, T. & Kaklamanis, C. (eds.). Berlin, Heidelberg: Springer, p. 302-315 14 p. (Lecture Notes in Computer Science; vol. 4368).

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

    2 Citations (Scopus)

Cite this