0

In the greedy Traveling Salesman algorithm, the algorithm starts from a starting vertex $v_1 = s$, and in $i$th stage, it goes to the closest vertex to $v_i$ that was not visited yet.

I want to find a counter example that the greedy traveling salesman does not provide any constant factor approximation to the TSP with triangle inequality.

Formally, for any constant $c > 0$, find a complete graph $G$, and positive weights on its edges, such that the weights obey the triangle inequality, and the length of the greedy TSP is by a factor of (at least) $c$ longer than the length of the shortest TSP of $G$.

An intuitive example is, say, if we design the weights of the edges so that the last edge of the greedy path(where it cannot make other choices) is arbitrarily large, but that violates the triangle inequality.

Thanks!

ztcnkdx
  • 21
  • Are you allowed to choose the starting vertex, or does the counterexample have to work regardless of starting vertex? – Joppy Oct 22 '18 at 00:50
  • Choosing starting vertex is allowed. The counter example does not need to work for all starting vertices. – ztcnkdx Oct 22 '18 at 05:13

0 Answers0