Voulez-vous effacer les recherches récentes ?

Toutes les recherches récentes seront supprimées

Regarder en plein écran

[MPRI 2.11.1] Algorithmes avancés 2014.10.23 Cours n°4(B/C)

Nicolas Schabanel
il y a 5 ans|33 vues
Cours 2.11.1 du Mastère de Recherches en Informatique
Algorithmes avancés - Nicolas Schabanel

Cours n°4 - Partie B/C
Introduction à la programmation semi-définie
• De la formulation quadratique d'un problème à la formulation sous forme d'un programme vectoriel
• Technique d'arrondi : Couper suivant un hyperplan pour Max-Cut
• Une O(n^1/3)-approximation pour le coloriage de graphes 3-colorables

TD n°4
• Tirage d'un vecteur unitaire aléatoire uniforme
• Une O(n^1/4)-approximation pour le coloriage de graphes 3-coloriables

Vidéos à découvrir