Approximation Algorithms

To avoid drawbacks of classical optimization techniques (high complexity for exact techniques and no guaranty for heuristics), approximation algorithms have been introduced a few decades ago. The idea is to relax the constraint of obtaining an exact solution and to propose polynomial time algorithms for which the quality of the output can be analytically compared to the optimal solution. Hence, they provide a theoretical and a practical framework for addressing (some) NP-complete problems solving.