I got stuck with the following question:
Consider the following heuristic: Start with a tour containing only one vertex. At each step, find the vertex outside the tour with the lesser distance to some vertex of the tour. Let v be the outter vertex and u be the inner vertex. Add v right after u in the tour. After adding all vertex, connect the last and the first one through their edge. Suppose that your edges follow the triangle distance property. How can we show that this heuristic is a 2-approximation for the TSP-metric problem?
Does anyone know how to start that?
Thanks in advance