Approximation algorithms for multi-criteria traveling salesman problems

Bodo Manthey*, L. Shankar Ram

*Corresponding author for this work

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

2 Citations (Scopus)

Abstract

In multi-criteria optimization, several objective functions are to be optimized. Since the different objective functions are usually in conflict with each other, one cannot consider only one particular solution as optimal. Instead, the aim is to compute so-called Pareto curves. Since Pareto curves cannot be computed efficiently in general, we have to be content with approximations to them. We are concerned with approximating Pareto curves of multi-criteria traveling salesman problems (TSP). We provide algorithms for computing approximate Pareto curves for the symmetric TSP with triangle inequality (Δ-STSP), symmetric and asymmetric TSP with strengthened triangle inequality (Δ(γ)-STSP and Δ(γ) -ATSP), and symmetric and asymmetric TSP with weights one and two (STSP(1,2) and ATSP(1,2)).

We design a deterministic polynomial-time algorithm that computes (1+γ+ε)-approximate Pareto curves for multi-criteria Δ(γ)-STSP for γ∈[1/2, 1]. We also present two randomized approximation algorithms for multi-criteria Δ(γ)-STSP achieving approximation ratios of 2γ32+2γ-1/2γ2+ ε and 1+γ/1+3γ-4γ2 + ε, respectively. Moreover, we design randomized approximation algorithms for multi-criteria Δ(γ) -ATSP (ratio 1/2 + γ3/1-3γ2 + ε for γ<1/√3), STSP(1,2) (ratio 4/3) and ATSP(1,2) (ratio 3/2). The algorithms for Δ;(γ)-ATSP, STSP(1,2), and ATSP(1,2) as well as one algorithm for Δ(γ) -STSP are based on cycle covers. Therefore, we design randomized approximation schemes for multi-criteria cycle cover problems by showing that multi-criteria graph factor problems admit fully polynomial-time randomized approximation schemes.

Original languageEnglish
Title of host publicationApproximation and Online Algorithms
Subtitle of host publication4th International Workshop, WAOA 2006, Revised Papers
EditorsThomas Erlebach, Christos Kaklamanis
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages302-315
Number of pages14
ISBN (Electronic)978-3-540-69514-1
ISBN (Print)978-3-540-69513-4
DOIs
Publication statusPublished - 1 Dec 2007
Externally publishedYes
Event4th Workshop on Approximation and Online Algorithms, WAOA 2006 - ETH Zürich, Zurich, Switzerland
Duration: 14 Sep 200615 Sep 2006
Conference number: 4

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume4368
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th Workshop on Approximation and Online Algorithms, WAOA 2006
Abbreviated titleWAOA 2006
CountrySwitzerland
CityZurich
Period14/09/0615/09/06
Otherpart of ALGO 2006

Keywords

  • Approximation algorithms
  • Approximation ratio
  • Travel salesman problem
  • Hamiltonian cycle

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

  • Cite this

    Manthey, B., & Ram, L. S. (2007). Approximation algorithms for multi-criteria traveling salesman problems. In T. Erlebach, & C. Kaklamanis (Eds.), Approximation and Online Algorithms: 4th International Workshop, WAOA 2006, Revised Papers (pp. 302-315). (Lecture Notes in Computer Science; Vol. 4368). Berlin, Heidelberg: Springer. https://doi.org/10.1007/11970125_24