| Randomized Rounding |
|
|
|
|
|
|
|
|
|
|
| l | Given
LP solution values xvw |
||||||||
| l | Build graph where
vw is present with |
||||||||
| probability xvw |
|||||||||
| l | Expected
cost is at most opt: S xvw cvw |
||||||||
| l | Expected number
of edges crossing any |
||||||||
| cut satisfies
constraint |
|||||||||
| l | If expected
number large for every cut, |
||||||||
| sampling theorem
applies |
|||||||||