Applicability of approximation algorithms vs meta-heuristics in practice

Question

How useful are approximation algorithms over say, metaheuristics or even problem-specific heuristics in practice?

Let's say a certain NP-hard minimization problem (take the travelling salesman problem (TSP) for example). It has a 2-approximation algorithm. This means, we are providing a fast algorithm which is at worst 100% inferior to the optimal solution. For a practitioner, we are saying that if the fastest tour is 100 miles long, then my tour will, at worst be 200 miles long. But this seems to be as bad a guarantee as no guarantee at all. However, the attention that approximation algorithms get from the academia is much more than, say, heuristics (without guarantees).

On a side note, why don't analysis evolve to consider the sub-family/distribution of instances that occur in practice and provide much stronger guarantees over such a subfamily?

Answer 1

Well, practitioners, as far as I have noticed, do not show a very stark difference between heuristics and approximation algorithms.

The upside that the approximation algorithms community provides with the solution quality guarantee is that the algorithm does not systematically miss some structure in the problem, making some solutions very bad in practice. Nevertheless, people do empirical tests on such algorithms before adopting. Secondly, proving hardness results like APX-hardness show limitations of any algorithm (including heuristic algorithms).

On your second suggestion on considering a probability distribution over instances - this is generally very complicated. Either it is difficult to justify in practice that the distribution of instances considered in the analysis is truly representative of reality; or it is difficult to do interesting analysis on a more realistic distribution.

Finally, on the interest of academia - I am not fully sure that more people are interested in approximation algorithms over heuristics in academia either. Nevertheless, it is possible to perceive a greater interest on approximation algorithms because it is fun to see and provide theoretically beautiful and surprising results.

Answer 2

In academia, theorists are interested in what they can prove to work on all inputs.

In industry, practitioners are interested in what works well enough on most of the cases they have to deal with in their day-to-day life.

There can be a big gap between the two. The methods used in practice might not have any worst-case guarantees, or it might be very very challenging to prove anything about them. To come up with an algorithm with theoretical guarantees, we often have to structure it in a way that is designed more towards supporting proof than necessarily working well in practice.

Theoretical analysis doesn't evolve to cover those practical algorithms because it is far too hard to prove anything interesting about the practical algorithms. Indeed, in many cases proofs probably are not the right tool for understanding those practical algorithms.

As far as the usefulness of approximation algorithms vs heuristics, it depends on the problem, and it's not possible to give any general answer that applies to all problems.

Answer 3

I find it weird that none of the previous answers mention the obvious trivial approach that anyone can take in practice, which is to run both a heuristic (or meta-heuristic) and an approximation algorithm and simply take the better solution. Then you get the goodness guarantee of the approximation algorithm and the likely higher goodness of the heuristic.