MIT
72
The Problem
lCut sampling
relied on Chernoff bound
lChernoff
bounds required that no one edge is a large fraction of the expectation
of a cut it crosses
lIf 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!