### 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 |
---|---|

Title of host publication | Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011) |

Editors | Mitsunori Ogihara, Jun Tarui |

Place of Publication | London |

Publisher | Springer |

Pages | 264-275 |

Number of pages | 12 |

ISBN (Print) | 978-3-642-20876-8 |

DOIs | |

Publication status | Published - 2011 |

Event | 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 - Tokyo, Japan Duration: 23 May 2011 → 25 May 2011 Conference number: 8 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 6648 |

### Conference

Conference | 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 |
---|---|

Abbreviated title | TAMC 2011 |

Country | Japan |

City | Tokyo |

Period | 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