Analysis of a near-metric TSP approximation algorithm

Sacha Krug

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

  • Volume: 47, Issue: 3, page 293-314
  • ISSN: 0988-3754

Abstract

top
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 3β2/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 also be used 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.

How to cite

top

Krug, Sacha. "Analysis of a near-metric TSP approximation algorithm." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 47.3 (2013): 293-314. <http://eudml.org/doc/273084>.

@article{Krug2013,
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 3β2/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 also be used 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.},
author = {Krug, Sacha},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {traveling salesman problem; combinatorial optimization; approximation algorithms; graph theory},
language = {eng},
number = {3},
pages = {293-314},
publisher = {EDP-Sciences},
title = {Analysis of a near-metric TSP approximation algorithm},
url = {http://eudml.org/doc/273084},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Krug, Sacha
TI - Analysis of a near-metric TSP approximation algorithm
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 3
SP - 293
EP - 314
AB - 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 3β2/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 also be used 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.
LA - eng
KW - traveling salesman problem; combinatorial optimization; approximation algorithms; graph theory
UR - http://eudml.org/doc/273084
ER -

References

top
  1. [1] H.-C. An, R. Kleinberg and D.B. Shmoys, Improving Christofides’ algorithm for the s-t path TSP. In Proc. of the 44th symposium on Theory of Computing (STOC 2012) 875–886. Zbl1286.68173
  2. [2] T. Andreae, On the Traveling Salesman Problem Restricted to Inputs Satisfying a Relaxed Triangle Inequality. Networks38 (2001) 59–67. Zbl0996.90086MR1852364
  3. [3] M.A. Bender and C. Chekuri, Performance guarantees for the TSP with a parameterized triangle inequality. Inf. Proc. Lett.73 (2000) 17–21. Zbl1063.68700MR1741501
  4. [4] H.-J. Böckenhauer and J. Hromkovič, Stability of approximation algorithms or parameterization of the approximation ratio. In Proc. of the 9th International Symposium on Operations Research in Slovenia (SOR 2007) 23–28. Zbl1147.90417MR2655336
  5. [5] H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert and W. Unger, Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Theor. Comput. Sci.285 (2002) 3–24. Zbl1094.90036MR1925784
  6. [6] H.-J. Böckenhauer, J. Hromkovič and S. Seibert, Stability of Approximation. In Handbook of Approximation Algorithms and Metaheuristics, edited by T.F. Gonzalez. Chapman & Hall, Boca Raton (2007). MR2307955
  7. [7] N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388. Carnegie Mellon University, Graduate School of Industrial Administration (1976). 
  8. [8] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms. MIT Press, Cambridge (2009). Zbl1187.68679MR2572804
  9. [9] L. Forlizzi, J. Hromkovič, G. Proietti and S. Seibert, On the Stability of Approximation for Hamiltonian Path Problems. Alg. Oper. Res.1 (2006) 31–45. Zbl1148.05040MR2276323
  10. [10] E.G. Goodaire and M.M. Parmenter, Discrete Mathematics with Graph Theory. Prentice Hall, Upper Saddle River (2005). Zbl0946.05001
  11. [11] J.A. Hoogeveen, Analysis of Christofides’ heuristic: Some paths are more difficult than cycles. Oper. Res. Lett.10 (1991) 291–295. Zbl0748.90071MR1122332
  12. [12] J. Hromkovič, Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, Heidelberg (2004). Zbl1069.68642
  13. [13] S. Krug, Analysis of Approximation Algorithms for the Traveling Salesman Problem in Near-Metric Graphs. Master’s thesis. ETH Zurich, Department of Computer Science (2011). 
  14. [14] T. Mömke, Structural Properties of Hard Metric TSP Inputs. In Proc. 37th Int. Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011) 394–405. Zbl1298.90089

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.