Voir la notice de l'article provenant de la source Numdam
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.
@article{ITA_2013__47_3_293_0,
author = {Krug, Sacha},
title = {Analysis of a near-metric {TSP} approximation algorithm},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {293--314},
publisher = {EDP-Sciences},
volume = {47},
number = {3},
year = {2013},
doi = {10.1051/ita/2013040},
mrnumber = {3103129},
zbl = {1286.90131},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2013040/}
}
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 SP - 293 EP - 314 VL - 47 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2013040/ DO - 10.1051/ita/2013040 LA - en ID - ITA_2013__47_3_293_0 ER -
%0 Journal Article %A Krug, Sacha %T Analysis of a near-metric TSP approximation algorithm %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2013 %P 293-314 %V 47 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2013040/ %R 10.1051/ita/2013040 %G en %F ITA_2013__47_3_293_0
Krug, Sacha. Analysis of a near-metric TSP approximation algorithm. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 3, pp. 293-314. doi: 10.1051/ita/2013040
Cité par Sources :