alt Hacker NewsSometimes you don't need an _exact_ solution. approximation of the traveling salesman problem exists for the metric version, it's O(n^3), and produces a result that's not worse than 50% of the optimal result, and for the general case O(n^2) algorithm exists that produces a result that costs at most twice the optimal result.
Replies
hyperpape • yesterday at 11:22 PM
Twice the optimal result is terrible, though.
Luckily, there are pretty good heuristic solutions that work well in practice.
➕ show 1 reply
For traveling salesman that's more than good enough. But in many cases an O(n^3) algorithm can't be used because n is in the billions. I remember interviewing a candidate who asserted that register retiming in digital circuits was a non-problem, so they were surprised that we were still working on improvements, because they had learned that the Leiserson-Saxe algorithm gives an optimal solution in O(n^3) time. But because real circuits are so large that that approach can't be used. Polynomial time often isn't good enough; even quadratic time often isn't tolerable.