| Random Sampling |
|
|
|
|
|
|
|
|
|
|
|
| l | [Gabow] scheme
great if m, c small |
|||||||||
| l | Random sampling |
|||||||||
| » | reduces m, c |
|||||||||
| » | scales cut values
(in expectation) |
|||||||||
| » | if pick half the
edges, get half of each cut |
|||||||||
| l | So find tree
packings, cuts in samples |
|||||||||
| Problem:
maybe some large deviations |