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
Watch video MaxSat by LP Rounding online without registration, duration hours minute second in high quality. This video was added by user Algorithms Lab 31 December 2023, don't forget to share it with your friends and acquaintances, it has been viewed on our site 640 once and liked it 21 people.