MIT
68
k-connected subgraph
lFractional
solution is k-connected
lSo every cut
has (expected) k edges crossing in rounded
solution
lSampling theorem says every cut has at least
k-(k log n)1/2 edges
lClose
approximation for large k
lCan
often repair: e.g., get k-connected subgraph at cost 1+((log n)/k)1/2 times min