Week 1

• Introduction to the module

• Minimum vertex cover

• Some basic facts about linear programs

• Minimum set cover

Week 2

• LP-duality

• Analyzing the greedy algorithm for minimum set cover via dual fitting

Week 3

• Complementary Slackness

• Primal-Dual approximation algorithm for minimum set cover

• Primal-Dual approximation algorithm for minimum knapsack cover

Week 4

• Basic concepts from discrete probability

Week 5

• Randomized rounding for set cover

• Chernoff bounds

Week 6

• Analysis of randomized rounding for set cover using Chernoff Bounds

• Randomized algorithm for MAX-CUT

Week 7

• Derandomization via conditional expectations