The Problem
l
Cut sampling relied on Chernoff bound
l
Chernoff bounds required that no one
edge is a large fraction of the
expectation of a cut it crosses
l
If sample rate
<<1
/
c
, each edge across
a min-cut is too significant
But: if edge only crosses large cuts,
then sample rate
<<1
/
c
is OK!