<p>I have implemented the nearest neighbor heuristic for solving symmetric TSP problems.
I was wondering if there is any relation between the solution found by the heuristic and the optimal solution? </p>

<p>Can we state theoretically how much higher the route length is in a worst case scenario?</p>

<p>Same question for simulated annealing, tabu-search and 2-opt search.</p>

CC BY-SA 3.0
2013-11-17T19:31:36.473Z
Related: http://cstheory.stackexchange.com/questions/18307/approximation-for-metric-tsp-worst-case-using-nearest-neighbor-heuristic, see also: http://cstheory.stackexchange.com/questions/19822/heuristics-for-tsp-without-triangle-inequality
Jennifer Ng
CC BY-SA 3.0
2013-11-17T19:39:24.473Z
I'm sorry, but 'quite well' is not really a theoretical upper bound...
user19553
CC BY-SA 3.0
2013-11-17T19:45:39.083Z
Potentially related as well: http://cstheory.stackexchange.com/questions/3727/a-simple-approximation-algorithm-for-the-tsp
Matthias
CC BY-SA 3.0
2013-11-17T19:49:06.303Z
For 2-opt check [Chandra, Karloff, and Tovey 1999]. Lower bound is Omega(log(n)/loglog(n)).
Matthias
CC BY-SA 3.0
2013-11-22T02:12:59.627Z
It can be far from optimal by logarithmic factor. This stated in a first linked question.
Saeed
<tsp><greedy-algorithms>
Worst case of heuristics for symmetric TSP
user19553
# Worst case of heuristics for symmetric TSP

(Asked by: username_0 on 2013-11-17)

I have implemented the nearest neighbor heuristic for solving symmetric TSP problems.
I was wondering if there is any relation between the solution found by the heuristic and the optimal solution?

Can we state theoretically how much higher the route length is in a worst case scenario?

Same question for simulated annealing, tabu-search and 2-opt search.

**Tags:** tsp, greedy-algorithms
> **Comments:**
> **username_1**: Related: http://cstheory.stackexchange.com/questions/18307/approximation-for-metric-tsp-worst-case-using-nearest-neighbor-heuristic, see also: http://cstheory.stackexchange.com/questions/19822/heuristics-for-tsp-without-triangle-inequality  
> **username_0**: I'm sorry, but 'quite well' is not really a theoretical upper bound...  
> **username_2**: Potentially related as well: http://cstheory.stackexchange.com/questions/3727/a-simple-approximation-algorithm-for-the-tsp  
> **username_2**: For 2-opt check [Chandra, Karloff, and Tovey 1999]. Lower bound is Omega(log(n)/loglog(n)).  
> **username_3**: It can be far from optimal by logarithmic factor. This stated in a first linked question.  

---

## 0 answers

