| Integer Linear Program |
|
|
|
|
|
|
|
|
|
|
| l | Variable
xvw=1 if buy edge vw |
||||||||
| l | Solution
cost S xvw cvw |
||||||||
| l | Constraint:
for every cut, S xvw ³ k |
||||||||
| l | Relaxing
integrality gives tractable LP |
||||||||
| » | Exponentially
many cuts |
||||||||
| » | But separation
oracles exist (eg min-cut) |
||||||||
| l | What is
integrality gap? |
||||||||