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

Cours 2.11.1 du Mastère de Recherches en Informatique
Algorithmes avancés - Nicolas Schabanel

Cours n°1 - Partie A/C
Introduction aux algorithmes d'approximation
• NP-complétude, PCP et Inapproximabilité
• Définitions: Problèmes d'optimisation et approximation
• Inapproximabilité du TSP non-métrique
• Une 2-approximation pour le TSP métrique
• Une 3/2-approximation pour le TSP métrique

TD n°1
• Dérandomisation par la méthode de l'espérance conditionnelle appliquée à Max-Cut
• Une O(√n)-approximation pour le coloriage de graphes 3-coloriables