MIT
89
First Try
lSuppose
current flow value f
»residual flow value v-f
lLemma: if all edges sampled
with probability rv/c(v-f) then, w.h.p., all directed
cuts within e of expectations
»Original
undirected sampling used r/c
lExpectations
nonzero, so no empty cut
lSo,
some augmenting path exists