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.09.25 Cours n°2(C/C)

Nicolas Schabanel
il y a 5 ans|16 vues
Cours 2.11.1 du Mastère de Recherches en Informatique
Algorithmes avancés - Nicolas Schabanel
Cours n°2 - Partie C/C [25/9/2014]
Introduction to Integer Programming, Linear Relaxation and Rounding
• Max-SAT
• Random solution to Max-SAT
• A (1-1/e)-approximation based on a randomized rounding of a solution to a linear program for Max-SAT
• Mixing both algorithms yield a 3/4-approximation

Exercise session 2 (to return on 11/10/2014)
• Dumb algorithm for Max-SAT
• Simple rounding f-approximation for Set Cover
• Randomized rounding (ln(n)+O(1))-approximation for Vertex Cover
• 2- and 3-approximations for Minimum Weighted Sum of Completion Time Scheduling with dependencies and with and without release dates

Vidéos à découvrir