MIT
67
Randomized Rounding
lGiven LP
solution values xvw
lBuild graph
where vw is present with probability xvw
lExpected cost
is at most opt: S xvw cvw
lExpected
number of edges crossing any cut satisfies constraint
lIf expected
number large for every cut, sampling theorem applies