Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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) 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.
