# 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 language Undefined Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011) Mitsunori Ogihara, Jun Tarui London Springer 264-275 12 978-3-642-20876-8 https://doi.org/10.1007/978-3-642-20877-5_27 Published - 2011 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 - Tokyo, JapanDuration: 23 May 2011 → 25 May 2011Conference number: 8

### Publication series

Name Lecture Notes in Computer Science Springer Verlag 6648

### Conference

Conference 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 TAMC 2011 Japan Tokyo 23/05/11 → 25/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