[MPRI 2.11.1] Algorithmes avancés 2014.10.16 Cours n°3(A/C)

Cours 2.11.1 du Mastère de Recherches en Informatique <br />Algorithmes avancés - Nicolas Schabanel <br />Cours n°3 - Partie A/C [16/10/2014] <br />PTAS: Schémas d'Approximation Polynomial <br />• Le voyageur de commerce euclidien (Euclidean TSP) <br /> <br />Exercise session 3 (to return on 23/10/2014) <br />• A Fully Polynomial Time Approximation Scheme for the Knapsack problem <br />• A Constant Time Approximation Scheme for Maximal Matching Size in undirected constant degree graphs