0
$\begingroup$

Having a hard time formulating the proof for this. The professor kinda breezed through the problems and I just want an explanation on how best to tackle this and how one would prove what it's desiring:

"Consider the following heuristic for building an approximate TSP cycle for a graph that satisfies the triangle inequality. Begin with an arbitrary node. At each step, choose the vertex u which is not in the current cycle, but has the smallest distance to any vertex in the current cycle. Add u to the cycle and repeat until all the nodes are in the cycle. Prove that this heuristic outputs a tour with a cost which is not more than twice the cost of an optimal tour."

$\endgroup$
  • $\begingroup$ Do you have any ideas at all? There is no magic formula for solving problems. $\endgroup$ – Yuval Filmus Oct 31 '14 at 21:05
  • $\begingroup$ Also, I don't understand the algorithm. How do you add $u$ to the cycle? $\endgroup$ – Yuval Filmus Oct 31 '14 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.