First Try
l Suppose current flow value f
» residual flow value v-f
l Lemma: 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
l Expectations nonzero, so no empty cut
l So, some augmenting path exists