MIT
66
Integer Linear Program
lVariable
xvw=1
if buy edge vw
lSolution
cost S xvw cvw
lConstraint:
for every cut, S xvw ³ k
lRelaxing
integrality gives tractable LP
»Exponentially
many cuts
»But
separation oracles exist (eg min-cut)
lWhat
is integrality gap?