 |
 |
8 of 18 |  |
 |
 |
MIT
Random Sampling
l
Theorem
[K]: Pick each edge with
probability 1/
c. Then all cuts are near
expected values
»
new min
-cut is O
*
(1)
»
original min
-cut is near
-minimum
l
Packing algorithms are fast---
O
*
(m)
»
saturate new min-cut
»
nearly saturate original min
-cut