MaxSat by LP Rounding
We take a look at 2 randomized algorithms for Maximum Satisfiability (MaxSat): First simply randomly setting the variables, and then solving the relaxed LP for MaxSat and setting the variables by "randomized rounding". We analyze both algorithms, and show that the combination of both gives us a 0.75-approximation. Further, we get to know conditional expectations as technique for derandomizing randomized algorithms.
00:00 MaxSat
01:51 Simple Randomized Algorithm
06:16 Derandomization
15:47 ILP for MaxSat
18:47 Randomized Rounding
20:53 Mathematical Tools
22:41 Analysis of Randomized Rounding
29:41 Combined Algorithm
33:52 Visualization of Bound
35:46 Wrap-Up