1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Given a cycle $v_1v_2\ldots v_nv_1$, inserting a new vertex $v_{n+1}$ after $v_n$ will give you $v_1v_2\ldots v_nv_{n+1}v_1$. There are no repeated vertices. $\endgroup$
    – avakar
    Commented Nov 19, 2013 at 7:15
  • 1
    $\begingroup$ Also, you cannot prove something that doesn't hold. Is the graph metric by any chance? $\endgroup$
    – avakar
    Commented Nov 19, 2013 at 7:18
  • 1
    $\begingroup$ Have you tried asking whoever gave you the problem? $\endgroup$
    – D.W. ♦
    Commented Nov 19, 2013 at 8:49

1 Answer 1

Reset to default
0
$\begingroup$

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)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It seems this version of the problem leaves out that the cost function should satisfy the triangel inequality. However, I'm confused because say we have this graph en.wikipedia.org/wiki/File:Minimum_spanning_tree.svg and we start with the leftmost node, won't we get the path shown? $\endgroup$
    – mlstudent
    Commented Nov 19, 2013 at 16:38
  • $\begingroup$ Oh, I understand it now. I didn't realize that you can make an edge between any two nodes. $\endgroup$
    – mlstudent
    Commented Nov 19, 2013 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.