Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
On the Approximation Ratio of the Path Matching Christofides Algorithm
verfasst von : Sacha Krug
Erschienen in: SOFSEM 2012: Theory and Practice of Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.