Sometimes 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.
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.
Twice the optimal result is terrible, though.
Luckily, there are pretty good heuristic solutions that work well in practice.
That's worst case. It means the most adversarial graph imaginable gets a time twice as long as the shortest possible.
If you allow twice the solution, you can do it in O(m log n) time using MST.