Questão 5 — When 1.5 Beats 2: The Strength of Christofides under the Triangle Inequality
Consider a symmetric, weighted, complete graph \( G = (V, E) \) with \( |V| = 6 \) vertices that satisfies the triangle inequality. The minimum spanning tree (MST) of \( G \) has total cost \( c(T) = 60 \). Two algorithms are applied to this graph:
- Rosenkrantz–Stearns–Lewis (RSL)
Finds \( T=\mathrm{mst}(G) \); doubles each edge of \(T\) to get an Eulerian multigraph \(T'\); finds an Euler tour and removes repeated vertices.
Performance guarantee: \( c(C_{\mathrm{RSL}}) \le 2\,c(TSP^*) \). - Christofides
Finds \( T=\mathrm{mst}(G) \); lets \( S \) be the set of odd-degree vertices of \(T\); finds a minimum perfect matching \( M \) on \(S\); adds \(M\) to \(T\) to get an Eulerian multigraph \(T'\); finds an Euler tour and removes repeated vertices.
Performance guarantee: \( c(C_{\mathrm{Chr}}) \le 1.5\,c(TSP^*) \).
Answer in one go:
(i) the maximum total cost \( c(C_{\mathrm{RSL}}) \) of the tour produced by (1);
(ii) the maximum total cost \( c(C_{\mathrm{Chr}}) \) of the tour produced by (2);
(iii) the improvement (in percentage) of Christofides over the RSL upper bound in the worst case;
(iv) whether equality \( c(C_{\mathrm{Chr}}) = 1.5\,c(TSP^*) \) can be achieved for some metric graphs.
Choose one option:
a) \( c(C_{\mathrm{RSL}})=120,\; c(C_{\mathrm{Chr}})=90,\; \text{improvement}=25\%,\; \text{equality possible.} \)
b) \( c(C_{\mathrm{RSL}})=120,\; c(C_{\mathrm{Chr}})=90,\; \text{improvement}=25\%,\; \text{equality not possible.} \)
c) \( c(C_{\mathrm{RSL}})=2c(T),\; c(C_{\mathrm{Chr}})=1.5c(T),\; \text{improvement}=25\%,\; \text{bound tight only for specific metric graphs.} \)
d) \( c(C_{\mathrm{RSL}})=c(C_{\mathrm{Chr}})=2c(T),\; \text{no improvement, bounds coincide.} \)
e) None of the above.
Original idea by: Luiza Barguil — at October 31, 2025
Labels: Traveling Salesperson Problem, Christofides, Rosenkrantz–Stearns–Lewis, MST
Questão interessante, mas tem muitas perguntas, nem todas fáceis. Por exemplo, como saber se Christofides atinge exatamente 1.5 vezes o ótimo em algum grafo métrico?
ResponderExcluirProfessor, muito obrigada pela provocação, na verdade, ao formular a questão fiquei pensei nisso também.
ExcluirPoderia esclarecer se existe uma construção conhecida em que o algoritmo de Christofides atinge exatamente o limite de 1.5 vezes o ótimo?
Ou esse bound é apenas teórico, sem exemplo concreto de grafo métrico em que a igualdade aconteça?
Aproveito para perguntar também se quando falamos em grafo métrico, estamos nos referindo apenas aos grafos que satisfazem a desigualdade triangular ou há outras propriedades que o definem?