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)
