Appears in collection : Algorithm and programming / Algorithmique et programmation

Approximation methods and probabilistic algorithms are two important ways to obtain efficient algorithms giving approximate solutions to hard problems. We give some examples from optimization, counting and verification problems. Property testing is also a very efficient method to approximate verification problems. complexity - difficult problem - approximation - probabilistic approximation schemes - optimization - counting verification - property testing