Dimitri Watel
COMPLEXITY : APPROXIMATION ALGORITHMS
This course introduces the concept of polynomial approximability of optimization problems. We search for polynomial algorithms that solve optimization problems but do not necessarily return an optimal solution. In that case, we study how far the returned solution is from the optimal solution and we search for polynomial algorithms for which this distance, known as the approximation ratio, is never "huge". This technique is used to solve hard problems for which no exact polynomial algorithm is known. This course introduces the different way to define this distance, the reductions preserving the approximation ratio, the approximation schemes, and the different techniques to build approximation algorithms.
Courses
Course material
Slides
- Example of polynomial approximations
- Optimization problems and approximation algorithms
- Polynomial approximation and linear programming
- Inapproximability
Copyright © 2016, Dimitri Watel