| Optimization with Cuts |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| l | Cut values
determine solution of many |
||||||||||||
| graph
optimization problems: |
|||||||||||||
| » | min-cut /
max-flow |
||||||||||||
| » | multicommodity
flow (sort-of) |
||||||||||||
| » | bisection /
separator |
||||||||||||
| » | network
reliability |
||||||||||||
| » | network design |
||||||||||||
| Randomization helps solve these problems |
|||||||||||||