New answers tagged traveling-salesman
3
You might want to read the paper DIFFERENT VERSIONS OF THE SAVINGS METHOD FOR THE TIME LIMITED VEHICLE ROUTING PROBLEM[1] which gives time complexities between $O(n^3)$ and $O(n^2*\log(n))$ note that in these complexity analysis the number of nodes not $|V|$ is used. If i am not mistaken $|V| \leq n(n-1) \leq n^2$ so $O(n^2*\log(n))$ would agree with ...
6
There are some proofs of the contrary: whatever the starting point, your local search can be stuck in solutions far away from the optimum. Here "local" means that each iteration must be done in polynomial time. Check the seminal paper "On the Complexity of Local Search for the Traveling Salesman Problem" by Papadimitriou and Steiglitz on ...
3
I am not aware of such proof. I think your question may be meaningful given a specific improvement heuristic. For example, I worked on solving large scale VRP problems using genetic algorithms as the meta-heuristic and doing local search to improve solutions. In this case, randomly generated initial solutions performed much better for me than using well-...
1
There is a mathematically justified way of saying is better than the other. The expected time to solve over all problems. When the expected value can't be computed over the distribution of problems you care about you can sample that space and run both approaches for both. This is called benchmarking and with sufficient samples the benchmark numbers will ...
Top 50 recent answers are included