Linear Programming and ApproximationSeminar in Approximation Algorithms Linear ProgrammingLinear objective function and Linear constraints
Linear Programming – Examplex=(2,1,3) is a feasible solution
7 * 2 + 1 + 5 * 3 = 30 is an upper bound the optimum Lower BoundHow can we find a lower bound?
Lower BoundAnother example: Lower BoundAssign a non-negative coefficient yi to every primal inequality such that
Lower bound 10y1+6y2 LP DualityThe problem of finding the best lower bound is a linear program LP DualityFor every x and y: cTx bTy
Thus, Opt(primal) Opt(dual)
The dual of the dual is the primal Examplex=(7/4,0,11/4) and y=(2,1) are feasible solutions
7*7/4 + 0 + 5*11/4 = 10*2 + 6*1 = 26
Thus, x and y are optimal Max Flow vs. Min s,t-cutPath(s,t) - the set of directed paths from s to t.
Opt(Dual) = Opt(Min s,t-cut) LP-duality TheoremTheorem:
Opt(primal) is finite Opt(dual) is finite
If x* and y* are optimal
Conclusion: LP NPcoNP Weak Duality TheoremIf x and y are feasible
Complementary Slackness Conditionsx and y are optimal