For 10 points, name this NP-hard problem that involves minimizing the path that a person takes to visit every city on a given map.
A metric version of this problem is the subject of the Christofides algorithm. This problem may be solved by a generalization of 2-opt that involves pairwise exchange, the Lin-Kerninghan method. Yet another solution can be derived using the elastic net method, where a circle is repeatedly mapped and stretched in the plane. One solution to it is the Nearest Neighbor algorithm, which involves going from the current point to the adjacent edge with the lightest weight. It is equivalent to finding a Hamiltonian cycle in a graph, and the Chinese postman problem is a dual of this problem. For 10 points, name this NP-hard problem that involves minimizing the path that a person takes to visit every city on a given map.
A metric version of this problem is the subject of the Christofides algorithm.
{Traveling Salesman} problem