MIT
77
Nonuniform Sampling
lIdea: if an edge is k-strong,
then it is in a k-connected graph
lSo “safe” to
sample with probability 1/k
lProblem: if sample edges with
different probabilities, E[cut value] gets messy
lSolution: if sample e with probability pe, give
it weight 1/pe
lThen E[cut
value]=original cut value