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 γ-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of \(\min\{1+\gamma,\frac{2\gamma^{2}}{2\gamma^{2}-2\gamma +1}\}+\varepsilon\) and a randomized approximation algorithm that achieves a ratio of \(\frac{2\gamma^{3}+2\gamma^{2}}{3\gamma^{2}-2\gamma +1}+\varepsilon\) . In particular, we obtain a 2+ε 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 γ-triangle inequality (ratio \(\frac{1+\gamma}{1+3\gamma -4\gamma^{2}}+\varepsilon\) ), asymmetric TSP (ATSP) with γ-triangle inequality (ratio \(\frac{1}{2}+ \frac{\gamma^{3}}{1-3\gamma^{2}}+\varepsilon\) ), STSP with weights one and two (ratio 4/3) and ATSP with weights one and two (ratio 3/2).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Angel, E., Bampis, E., Gourvés, L.: Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem. Theor. Comput. Sci. 310(1–3), 135–146 (2004)
Angel, E., Bampis, E., Gourvés, L., Monnot, J.: (Non-)approximability for the multi-criteria TSP(1,2). In: Liśkiewicz, M., Reischuk, R. (eds.) Proc. of the 15th Int. Symp. on Fundamentals of Computation Theory (FCT). Lecture Notes in Computer Science, vol. 3623, pp. 329–340. Springer, New York (2005)
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, New York (1999)
Barahona, F., Pulleyblank, W.R.: Exact arborescences, matchings and cycles. Discret. Appl. Math. 16(2), 91–99 (1987)
Berman, P., Karpinski, M.: 8/7-approximation algorithm for (1,2)-TSP. In: Proc. of the 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 641–648. SIAM, Philadelphia (2006)
Bläser, M.: A 3/4-approximation algorithm for maximum ATSP with weights zero and one. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) Proc. of the 7th Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Lecture Notes in Computer Science, vol. 3122, pp. 61–71. Springer, New York (2004)
Bläser, M., Manthey, B., Sgall, J.: An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality. J. Discret. Algorithms 4(4), 623–632 (2006)
Böckenhauer, H.-J., Hromkovič, J., Klasing, R., Seibert, S., Unger, W.: Approximation algorithms for the TSP with sharpened triangle inequality. Inf. Process. Lett. 75(3), 133–138 (2000)
Chandran, L.S., Ram, L.S.: On the relationship between ATSP and the cycle cover problem. Theor. Comput. Sci. 370(1-3), 218–228 (2007)
Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA (1976)
Ehrgott, M.: Approximation algorithms for combinatorial multicriteria optimization problems. Int. Trans. Oper. Res. 7(1), 5–31 (2000)
Ehrgott, M.: Multicriteria Optimization. Springer, New York (2005)
Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectrum 22(4), 425–460 (2000)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)
Gilmore, P.C., Lawler, E.L., Shmoys, D.B.: Well-solved special cases. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, pp. 87–143. Wiley, New York (1985)
Gutin, G., Punnen, A.P. (eds.): The Traveling Salesman Problem and its Variations. Kluwer Academic, Dordrecht (2002)
Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.I.: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM 52(4), 602–626 (2005)
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.): The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York (1985)
Lovász, L., Plummer, M.D.: Matching Theory. North-Holland Mathematics Studies, vol. 121. Elsevier, Amsterdam (1986)
Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105–113 (1987)
Papadimitriou, C.H.: The complexity of restricted spanning tree problems. J. ACM 29(2), 285–309 (1982)
Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: Proc. of the 41st Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 86–92. IEEE Computer Society (2000)
Rosenkrantz, D.J., Stearns, R.E., Lewis II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6(3), 563–581 (1977)
Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347–352 (1954)
Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this work has been presented at the 4th Workshop on Approximation and Online Algorithms (WAOA 2006) (Lecture Notes in Computer Science, vol. 4368, pp. 302–315, 2007).
B. Manthey is supported by the Postdoc-Program of the German Academic Exchange Service (DAAD). He is on leave from Saarland University and has done part of the work at the Institute for Theoretical Computer Science of the University of Lübeck supported by DFG research grant RE 672/3 and at the Department of Computer Science at Saarland University.
Rights and permissions
About this article
Cite this article
Manthey, B., Shankar Ram, L. Approximation Algorithms for Multi-Criteria Traveling Salesman Problems. Algorithmica 53, 69–88 (2009). https://doi.org/10.1007/s00453-007-9011-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-007-9011-z