[2016 MPRI 2.11.1] 2. Mathematical Programming 1: Linear Programming & Randomized Rounding (2016/9/21)

MPRI - Parisian Master of Research in Computer Science
Course 2.11.1: Approximation Algorithms, Randomization & Nature Programming
Nicolas SCHABANEL, CNRS - Université Paris Diderot

LECTURE 2 (2016/09/21)
MATHEMATICAL PROGRAMMING 1: LINEAR PROGRAMMING

[0:00:00] 0. Mathematical Programming
[0:01:45] 1. Introduction to Linear Programming
[0:07:04] 2. First Example: Max-CUT as an Integer Program
[0:38:16] 3. LP Relaxation for Max-CUT & Randomized Rounding
[1:09:26] 4. Max-SAT: Random Assignment
[1:24:23] 5. Max-SAT: Randomized Rounding
[2:12:33] 6. Max-SAT: Combining both Algorithms into One
[2:23:37] 7. Exercises 2: Maximum Arc-Disjoint Paths (2)