Nonuniform Sampling
l Idea: if an edge is k-strong, then it is in
a k-connected graph
l So “safe” to sample with probability 1/k
l Problem: if sample edges with different
probabilities, E[cut value] gets messy
l Solution: if sample e with probability pe,
give it weight 1/pe
l Then E[cut value]=original cut value