MIT
86
Smoothing
lIf edge has
strength ce, divide into br / ce edges of capacity ce /br
»Creates
br å 1/ce =
brn
edges
lNow each edge is
only 1/br fraction of any cut of its
strong component
lSo sampling a 1/b
fraction works
lSo dividing into b
groups works
lYields (1-e) max-flow
in O*(mn1/2 / e) time