Main
Home
/
Tags
/
Seidel
Seidel
1 page tagged.
Computer science / Coursework / Randomized algorithms
Lecture 4.4: Design Methods IV
Relax an integer program to an LP/SDP, then round with coins: SetCover → O(ln n); MaxCut → Goemans–Williamson 0.878 via a random hyperplane. Then solving LP by randomization (Seidel, MSW, Clarkson).