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?