Abstract
The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the β-metric traveling salesman problem (Δ β -TSP), i.e., the TSP restricted to graphs satisfying the β-triangle inequality c({v,w}) ≤ β(c({v,u}) + c(u,w})), for some cost function c and any three vertices u,v,w. The well-known path matching Christofides algorithm (PMCA) guarantees an approximation ratio of \(\frac{3}{2}\beta^2\) and is the best known algorithm for the Δ β -TSP, for 1 ≤ β ≤ 2. We provide a complete analysis of the algorithm. First, we correct an error in the original implementation that may produce an invalid solution. Using a worst-case example, we then show that the algorithm cannot guarantee a better approximation ratio. The example can be reused for the PMCA variants for the Hamiltonian path problem with zero and one prespecified endpoints. For two prespecified endpoints, we cannot reuse the example, but we construct another worst-case example to show the optimality of the analysis also in this case.
This work was partially supported by SNF grant No. 200021-132510/1.
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
Andreae, T.: On the Traveling Salesman Problem Restricted to Inputs Satisfying a Relaxed Triangle Inequality. Networks 38, 59–67 (2001)
Bender, M.A., Chekuri, C.: Performance guarantees for the TSP with a parameterized triangle inequality. Inf. Proc. Letters 73, 17–21 (2000)
Böckenhauer, H.-J., Hromkovič, J.: Stability of approximation algorithms or parameterization of the approximation ratio. In: Proceedings of the 9th International Symposium on Operations Research in Slovenia, pp. 23–28 (2007)
Böckenhauer, H.-J., Hromkovič, J., Klasing, R., Seibert, S., Unger, W.: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Theoretical Computer Science 285, 3–24 (2002)
Böckenhauer, H.-J., Hromkovič, J., Seibert, S.: Stability of Approximation. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall, Boca Raton (2007)
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388. Carnegie Mellon University, Graduate School of Industrial Administration (1976)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)
Forlizzi, L., Hromkovič, J., Proietti, G., Seibert, S.: On the Stability of Approximation for Hamiltonian Path Problems. Alg. Oper. Res. 1, 31–45 (2006)
Goodaire, E.G., Parmenter, M.M.: Discrete Mathematics with Graph Theory. Prentice Hall, Upper Saddle River (2005)
Hoogeveen, J.A.: Analysis of Christofides’ heuristic: Some paths are more difficult than cycles. Oper. Res. Letters 10, 291–295 (1991)
Hromkovič, J.: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, Heidelberg (2004)
Krug, S.: Analysis of Approximation Algorithms for the Traveling Salesman Problem in Near-Metric Graphs. Master’s thesis, ETH Zurich, Department of Computer Science (2011)
Mömke, T.: Structural Properties of Hard Metric TSP Inputs. In: Černá, I., Gyimóthy, T., Hromkovič, J., Jefferey, K.G., Králović, R., Vukolić, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol. 6543, pp. 394–405. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krug, S. (2012). On the Approximation Ratio of the Path Matching Christofides Algorithm. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Turán, G. (eds) SOFSEM 2012: Theory and Practice of Computer Science. SOFSEM 2012. Lecture Notes in Computer Science, vol 7147. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27660-6_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-27660-6_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-27659-0
Online ISBN: 978-3-642-27660-6
eBook Packages: Computer ScienceComputer Science (R0)