<p>No, the NN heuristic does not have constant factor for metric TSP. </p>

<p>Rosenkrantz, Stearns, and Lewis proved in <a href="http://epubs.siam.org/doi/abs/10.1137/0206041">An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM J. Comput. 6(3): 563-581 (1977)</a> that the worst case ratio of the tour obtained by the nearest neighbor method is bounded above by a logarithmic function of the number of nodes.</p>

CC BY-SA 3.0
2013-07-09T17:02:06.227Z
2013-07-09T17:02:06.227Z
Jennifer Ng
<p>I'm looking at different heuristics that approximate solutions for a metric Traveling Salesman Problem. I was wondering if there is a worst case ratio of tours calculated by the nearest neighbor heuristic to the optimal tour.</p>

<p>Apparently, the Minimum Spanning Tree heuristic is a 2-approximation for metric TSPs meaning that it will only find tours that - in the worst case - are twice as long as the optimal tour. Is there some factor like this for the nearest neighbor heuristic for metric TSPs?</p>

<tsp><heuristics>
Approximation for metric TSP: Worst case using nearest neighbor heuristic?
Johannes
# Approximation for metric TSP: Worst case using nearest neighbor heuristic?

(Asked by: username_0 on 2013-07-09)

I'm looking at different heuristics that approximate solutions for a metric Traveling Salesman Problem. I was wondering if there is a worst case ratio of tours calculated by the nearest neighbor heuristic to the optimal tour.

Apparently, the Minimum Spanning Tree heuristic is a 2-approximation for metric TSPs meaning that it will only find tours that - in the worst case - are twice as long as the optimal tour. Is there some factor like this for the nearest neighbor heuristic for metric TSPs?

**Tags:** tsp, heuristics

---

## 1 answers

### Answer by username_1 on 2013-07-09. Score: 14 | Accepted answer

No, the NN heuristic does not have constant factor for metric TSP.

Rosenkrantz, Stearns, and Lewis proved in [An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM J. Comput. 6(3): 563-581 (1977)](http://epubs.siam.org/doi/abs/10.1137/0206041) that the worst case ratio of the tour obtained by the nearest neighbor method is bounded above by a logarithmic function of the number of nodes.


---

