[MPRI 2014] 1.24 Algorithmes randomisés (Cours n°2 - Partie A/C)

MPRI 1.24 - Algorithmes randomisés (Cours n°12 Partie A/C) - Nicolas Schabanel (CNRS, LIAFA)

Lecture 2: Thursday Jan 30, 8:45-11:45 - Approximation algorithms & Randomized Rounding
• Random solution for Max-SAT
• Linear program relaxation for Max-Sat and its randomized rounding
• Mixing both algorithms yields a better one

Exercise session 2: Randomized rounding
• A semi-definite program for Max-Cut and the random cut by a hyperplane
• Randomized rounding of a linear program relaxation for Set-Cover

URL: https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-1-24