 |
 |
27 of 32 |  |
 |
 |
MIT
Graph Approximation
l
Theorem: given any undirected graph
G
, there is a (capacitated) graph with
O
(n
(log n)
/
e
2
)
edges that approximates
all cuts in G
to within (1
±
e)
l
Note: no dependence on
c
l
Proof: probabilistic method
»
sample edges with varying probabilities
l
Is there a deterministic construction?