Deterministic algorithms for multi-criteria Max-TSP

Manthey, Bodo (2012) Deterministic algorithms for multi-criteria Max-TSP. Discrete Applied Mathematics, 160 (15). pp. 2277-2285. ISSN 0166-218X

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

Abstract:	We present deterministic approximation algorithms for the multi-criteria maximum traveling salesman problem (Max-TSP). Our algorithms are faster and simpler than the existing randomized algorithms. We devise algorithms for the symmetric and asymmetric multi-criteria Max-TSP that achieve ratios of 1/2k − $\varepsilon$ and 1/(4k−2) − $\varepsilon$ , respectively, where k is the number of objective functions. For two objective functions, we obtain ratios of 3/8 − $\varepsilon$ and 1/4 − $\varepsilon$ for the symmetric and asymmetric TSP, respectively. Our algorithms are self-contained and do not use existing approximation schemes as black boxes.
Item Type:	Article
Copyright:	© 2012 Elsevier
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/80971
Official URL:	http://dx.doi.org/10.1016/j.dam.2012.05.007
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Repository Staff Only: item control page