MPRI 2.11.1: Advanced Algorithms Course - Lecture 2 (B/C)

Cours 2.11.1 du Mastère de Recherches en Informatique
Algorithmes avancés - Nicolas Schabanel
Cours n°2 - Partie B/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