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

[img] PDF
Restricted to UT campus only
: Request a copy
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
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