Why using heuristics in an algorithm takes away asymptotic optimality?

Question

I was reading about some geometric routing algorithms, there it says that when employing heuristics in a version of the main algorithm it may improve performance, but takes away asymptotic optimality.

Why is that the case? Should we prefer asymptotic optimality over better performance? Are there prototypical cases where one should prefer asymptotic optimality? Are there any benchmarks known?

Answer 1

I think you are asking about optimization problems where heuristics run fast but might not achieve the totally optimal solution, whereas truly optimal solution finding algorithms can run much slower in the worst-case although they always give the totally optimal solution. If so, here's some info. In general, the decision to use a heuristic algorithm often depends on how well it approximates the optimal solution "in practice", and if this typical solution quality is good enough for you, and whether or not you think your particular problem instance falls into the category of the problems that are encountered in practice. If you are interested, you can look up approximation algorithms for NP-complete problems. There are some problems where the score of the solution found by a heuristic is within a constant multiplier (1 + epsilon) of the score of the optimal solution, and you can choose epsilon; however typically the running time increases as epsilon decreases.

Answer 2

My guess is that they are talking about use of (non-admissible) heuristics for approximation algorithms. For instance, the traveling salesman problem is NP-complete, yet there are heuristic approximation methods that are much faster than known algorithms for NP-complete problems but are only guaranteed to get within a few percent of optimal.