Considering the Traveling Salesman Problem (TSP) in a complete graph where the triangular inequality holds, which of the following statements most accurately describes the fundamental difference in tour construction and performance guarantee between the Rosenkrantz-Stearns-Lewis algorithm and the Christofides algorithm?
- Both algorithms are based on the "Farthest Insertion" heuristic, but Christofides applies additional optimization using dynamic programming to achieve a 1.5 x optimal cost guarantee, while Rosenkrantz-Stearns-Lewis does not.
- Christofides' algorithm uses minimum perfect matching over the odd degree nodes of the minimum spanning tree (MST) to construct an Eulerian graph, achieving an approximation guarantee of 1.5 x optimal cost. In contrast, the Rosenkrantz-Stearns-Lewis algorithm duplicates all edges of the MST, resulting in a guarantee of 2 x optimal cost.
- The Rosenkrantz-Stearns-Lewis algorithm duplicates the edges of the MST to form an Eulerian tour, and the Christofides algorithm improves on this by finding a minimum perfect match on all nodes in the graph (not just those of odd degree), but both algorithms share the same 2 x cost-optimal performance guarantee.
- The Rosenkrantz-Stearns-Lewis algorithm uses a minimum perfect match over the odd degree nodes of the MST, achieving a 1.5 x optimal cost guarantee, while the Christofides algorithm duplicates all MST edges, achieving a 2 x optimal cost guarantee.
- None of the above.
Original idea by: Juan Jose Rodriguez Rodriguez
No comments:
Post a Comment