Abstract
We present randomized approximation algorithms for multi-criteria traveling salesman problems (TSP), where some objective functions should be minimized while others should be maximized. For the symmetric multi-criteria TSP (STSP), we present an algorithm that computes (2/3 − ε, 4 + ε) approximate Pareto curves. Here, the first parameter is the approximation ratio for the objectives that should be maximized, and the second parameter is the ratio for the objectives that should be minimized. For the asymmetric multi-criteria TSP (ATSP), we present an algorithm that computes (1/2 − ε, log2 n + ε) approximate Pareto curves. In order to obtain these results, we simplify the existing approximation algorithms for multi-criteria Max-STSP and Max-ATSP. Finally, we give algorithms with improved ratios for some special cases.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angel, E., Bampis, E., Gourvés, L.: Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem. Theoret. 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.) FCT 2005. LNCS, vol. 3623, pp. 329–340. Springer, Heidelberg (2005)
Bläser, M., Manthey, B.: Approximating maximum weight cycle covers in directed graphs with weights zero and one. Algorithmica 42(2), 121–139 (2005)
Bläser, M., Manthey, B., Putz, O.: Approximating multi-criteria max-TSP. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 185–197. Springer, Heidelberg (2008)
Ehrgott, M.: Approximation algorithms for combinatorial multicriteria optimization problems. Int. Trans. Oper. Res. 7(1), 5–31 (2000)
Ehrgott, M.: Multicriteria Optimization. Springer, Heidelberg (2005)
Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectrum 22(4), 425–460 (2000)
Feige, U., Singh, M.: Improved approximation ratios for traveling salesperson tours and paths in directed graphs. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol. 4627, pp. 104–118. Springer, Heidelberg (2007)
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)
Manthey, B.: On approximating multi-criteria TSP. In: Proc. 26th Int. Symp. on Theoretical Aspects of Computer Science (STACS), pp. 637–648 (2009)
Manthey, B., Ram, L.S.: Approximation algorithms for multi-criteria traveling salesman problems. Algorithmica 53(1), 69–88 (2009)
Paluch, K., Mucha, M., Ma̧dry, A.: A 7/9 - approximation algorithm for the maximum traveling salesman problem. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009 and RANDOM 2009. LNCS, vol. 5687, pp. 298–311. Springer, Heidelberg (2009)
Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: Proc. 41st Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 86–92. IEEE, Los Alamitos (2000)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Manthey, B. (2010). Multi-Criteria TSP: Min and Max Combined. In: Bampis, E., Jansen, K. (eds) Approximation and Online Algorithms. WAOA 2009. Lecture Notes in Computer Science, vol 5893. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12450-1_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-12450-1_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12449-5
Online ISBN: 978-3-642-12450-1
eBook Packages: Computer ScienceComputer Science (R0)