Approximation algorithms for multi-criteria traveling salesman problems

Manthey, B. and Shankar Ram, L. (2009) Approximation algorithms for multi-criteria traveling salesman problems. Algorithmica, 53 (1). pp. 69-88. ISSN 0178-4617

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

Abstract:	We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with $\gamma$ -triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of $\min\left\{1+\gamma,{2\gamma^2\over 2\gamma^2-2\gamma +1}\right\} + \varepsilon$ and a randomized approximation algorithm that achieves a ratio of ${2\gamma^3 + 2\gamma^2\over 3\gamma^2-2\gamma +1} + \varepsilon$ . In particular, we obtain a $2+\varepsilon$ approximation for multi-criteria metric STSP. Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with $\gamma$ -triangle inequality ratio ${1\gamma\over 1+3\gamma-4\gamma^2}+ \varepsilon$ ), asymmetric TSP (ATSP) with $\gamma$ -triangle inequality (ratio ${1\over 2} + {\gamma^3\over 1-3\gamma^2}+ \varepsilon$ ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2).
Item Type:	Article
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/68059
Official URL:	http://dx.doi.org/10.1007/s00453-007-9011-z
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page