[MPRI 2.11.1] Advanced Algorithms - Lecture 2 (Part A/C)

Cours 2.11.1 du Mastère de Recherches en Informatique <br />Algorithmes avancés - Nicolas Schabanel <br />Cours n°2 - Partie A/C [25/9/2014] <br />Introduction to Integer Programming, Linear Relaxation and Rounding <br />• Max-SAT <br />• Random solution to Max-SAT <br />• A (1-1/e)-approximation based on a randomized rounding of a solution to a linear program for Max-SAT <br />• Mixing both algorithms yield a 3/4-approximation <br /> <br />Exercise session 2 (to return on 11/10/2014) <br />• Dumb algorithm for Max-SAT <br />• Simple rounding f-approximation for Set Cover <br />• Randomized rounding (ln(n)+O(1))-approximation for Vertex Cover <br />• 2- and 3-approximations for Minimum Weighted Sum of Completion Time Scheduling with dependencies and with and without release dates