2025-286

The Euclidean Traveling Salesman Problem (Euclidean TSP) is a special case of the symmetric TSP where each city corresponds to a point in \(\mathbb{R}^d\) and costs equal the Euclidean distance between points. As the Euclidean distance is symmetric and satisfies the triangle inequality, Euclidean TSP is a special case of Metric TSP, allowing approximation algorithms to be used for a solution.

Consider the Euclidean TSP on 5 cities, located in \(\mathbb{R}^2\) at

A (0, 0); B (2, 0); C (2, 1); D (0, 1); E (1, 1).

Which of the following statements is true?

1. The Nearest Neighbor heuristic starting from any node always yields a tour of cost 6.
2. Any Euclidean TSP can be solved in polynomial time using the ILP formulation.
3. The optimal tour is achieved by ABCED, costing 5.
4. The Cheapest Insertion heuristic is better than the Nearest Neighbor for any starting single-node cycle. 
5. None of the above

Original idea by: Daniel Gardin