 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
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
|
|