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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.