MIT
42
Random Sampling
lGabow’s
algorithm great if m, c small
lRandom
sampling
»reduces
m,
c
»scales
cut values (in expectation)
»if
pick half the edges, get half of each cut
lSo
find tree packings, cuts in samples
Problem:
maybe some large deviations