Deterministic algorithms for multi-criteria TSP

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

3 Citations (Scopus)

Abstract

We present deterministic approximation algorithms for the multi-criteria traveling salesman problem (TSP). Our algorithms are faster and simpler than the existing randomized algorithms. First, we devise algorithms for the symmetric and asymmetric multi-criteria Max-TSP that achieve ratios of 1/2k − ε and 1/(4k − 2) − ε, respectively, where k is the number of objective functions. For two objective functions, we obtain ratios of 3/8 − ε and 1/4 − ε for the symmetric and asymmetric TSP, respectively. Our algorithms are self-contained and do not use existing approximation schemes as black boxes. Second, we adapt the generic cycle cover algorithm for Min-TSP. It achieves ratios of 3/2 + ε, $\frac{1}{2} + \frac{\gamma^3}{1-3\gamma^2} +\varepsilon$, and $\frac{1}{2} + \frac{\gamma^2}{1-\gamma} +\varepsilon$ for multi-criteria Min-ATSP with distances 1 and 2, Min-ATSP with $\gamma$-triangle inequality and Min-STSP with $\gamma$-triangle inequality, respectively.
Original languageUndefined
Title of host publicationProceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011)
EditorsMitsunori Ogihara, Jun Tarui
Place of PublicationLondon
PublisherSpringer
Pages264-275
Number of pages12
ISBN (Print)978-3-642-20876-8
DOIs
Publication statusPublished - 2011
Event8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 - Tokyo, Japan
Duration: 23 May 201125 May 2011
Conference number: 8

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume6648

Conference

Conference8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011
Abbreviated titleTAMC 2011
CountryJapan
CityTokyo
Period23/05/1125/05/11

Keywords

  • METIS-277630
  • Multi-objective optimization
  • Multi-criteria optimization
  • Traveling Salesman Problem
  • IR-77041
  • EWI-20152
  • Approximation algorithms

Cite this

Manthey, B. (2011). Deterministic algorithms for multi-criteria TSP. In M. Ogihara, & J. Tarui (Eds.), Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011) (pp. 264-275). (Lecture Notes in Computer Science; Vol. 6648). London: Springer. https://doi.org/10.1007/978-3-642-20877-5_27