 |
 |
21 of 32 |  |
 |
 |
MIT
Sampling Theorem
l
Given graph G, build a
sample G
(p)
by
including each edge with probability p
l
Cut of value v
in G
has expected
value
pv
in
G(p)
l
Theorem:
With high probability, all cuts
in G
(9
ln
n / e
2c
)
have (1
±
e)
times their
expected values.