MIT
5
Optimization with Cuts
lCut values determine solution of many graph optimization problems:
»min-cut / max-flow
»multicommodity flow (sort-of)
»bisection / separator
»network reliability
»network design
lRandomization helps solve these problems
ok for ratio cuts b/#verts fixed.
ignore for this talk.