| 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 | Definition: “constant”
r = 8 (ln
n) / e2 |
||||||||
| l | Theorem: With high probability, all cuts |
||||||||
| in G(r / c) have (1 ± e) times their |
|||||||||
| expected values. |
|||||||||