Description

Algorithmes d'approximation, partie 2

Ceci est la suite des algorithmes d'approximation, partie 1. Ici, vous apprendrez la dualité de programmation linéaire appliquée à la conception de certains algorithmes d'approximation et la programmation semi-définie appliquée à Maxcut.

En suivant les deux parties de ce cours, vous serez exposé à un éventail de problèmes aux fondements de l'informatique théorique et à de puissantes techniques de conception et d'analyse. À la fin, vous serez en mesure de reconnaître, face à un nouveau problème d'optimisation combinatoire, s'il est proche de l'un des quelques problèmes de base connus, et pourrez concevoir des relaxations de programmation linéaire et utiliser l'arrondi aléatoire pour tenter de résoudre votre propre problème. Le contenu du cours et en particulier les devoirs sont de nature théorique sans aucune affectation de programmation.

Ceci est le deuxième d'un cours en deux parties sur les algorithmes d'approximation.

Prix: inscrivez-vous gratuitement!

Algorithmes d'approximation Partie II - École normale supérieure