Sometimes I see that people call a problem NP-hard and because of that refuse to create computer algorithms that directly solve it. I think I've never read actual benchmark results for such problems. Are there any? Are there any NP-complete problems with not very bad performance?
[Math] How slow are direct solutions of NP-complete problems on computers
algorithmscomputer sciencenp
Best Answer
This 2003 paper shows there has been quite a bit of work. The focus is on "fast" exponential-time solutions to NP-hard problems, including the TSP, SAT, knapsack problems, graph coloring, to mention a few:
For example, there is an exact algorithm for the Euclidean TSP in the plane (ETSP) with time complexity $O(2^{\sqrt{n} \log n})$. But as is well-known, S. Arora and J.S.B. Mitchell found PTAS's to solve ETSP.
This paper has been cited over 500 times since, showing there has been significant subsequent work.