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 (pp. pp. 264-275).

[img] PDF
Restricted to UT campus only
: Request a copy
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
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page