Deterministic algorithms for multi-criteria TSP

Manthey, Bodo (2011) Deterministic algorithms for multi-criteria TSP. In: 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011, 23-25 May 2011, Tokyo, Japan.

PDF
Restricted to UT campus only: Request a copy
354Kb

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.
Item Type:	Conference or Workshop Item
Copyright:	© 2011 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/77041
Official URL:	http://dx.doi.org/10.1007/978-3-642-20877-5_27
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page