I am studying the Travelling Sales Man problem:
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
And I wonder: given a list of cities/distances that the salesman must visit, is it possible to estimate the solution (shortest path) without finding it? Or is doing a rough estimate about as hard as finding the actual paths?
There are, see here. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are with a high probability just 2–3% away from the optimal solution.