[Solved]: Traveling Salesman's Tour Approx Algorithm: is this really a Hamiltonian Path?

Problem Detail: 

I'm given this problem:

Consider the following closest-point heuristic for building an approximate traveling-salesman tour. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex u that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest u is vertex v. Extend the cycle to include u by inserting u just after v. Repeat until all vertices are on the cycle. Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.

This is the same as Prim's algorithm. Unless I'm missing something, this is not an approximate traveling salesman tour since the traveling salesman requires a Hamiltonian path where we don't revisit any nodes, but on many graphs this algorithm seems to require revisiting nodes to get back to the source node. Am I wrong or is this problem unclearly worded?

Asked By : mlstudent

Answered By : David Richerby

You're wrong and the question is also unclearly worded. First, TSP is usually defined in terms of Hamiltonian cycles, not paths. That is, the salesman is in each city exactly once, except for the start point, which he is in twice. Second, as @avakar explains in his first comment, the algorithm given doesn't repeat vertices.

Also, the question seems to be making an unstated assumption. To flesh out @avakar's second comment, suppose you are given cities $1, \dots, n$ where:

• $d(i,n)=k$ for $i< n-2$
• $d(n-2,n)=d(n-1,n)=2$
• $d(n-2,i)=d(n-1,i)=0$ for $i<n$
• $d(i,j)=1$ for all other pairs $i$,$j$.

The optimal tours have cost $n$: e.g., $1, 2, \dots, n-2, n, n-1, 1$. However, the given algorithm will produce a tour like $1, n-1, n-2, 2, 3, \dots, n-3, n, 1$ when started at any vertex except $n$. This has cost $n-5+2k$, which is more than twice the optimum whenever $k>\tfrac12(n+5)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18147