Linear Programming, Duality and Rounding
Relaxing integer decisions to fractions gives a problem that can be solved, and its optimum bounds the integer one. Duality supplies the certificate that a solution is optimal, and rounding turns the fractional answer back into a real one at a cost that can be bounded.
What a learner can do afterwards
- Write a combinatorial problem as a linear program and state its dual
- Use a dual solution as a certificate for a bound on the primal
- Round a fractional solution and bound what the rounding lost
1 · Read
A linear program writes a decision problem in math. Pick variables for the choices you control, write the limits you face as linear inequalities, and write the goal as a linear expression over costs, profits, or resources. Practice the full path from a word problem to a clean program, since everything after starts from writing one with confidence.
Relaxing turns hard integer choices into easy fractions. For vertex cover, replace each take-or-skip 0 or 1 with a fraction between 0 and 1, then solve the easier fractional program. Its optimum bounds the integer one from below, so the fraction tells you how far any true answer can possibly go.
Every linear program owns a dual: a second program built from the same data whose any feasible value certifies a bound on the first. A good dual solution proves your answer sits near optimal without you ever knowing the optimum itself. Read the primal and the dual off the same matrix, and let the dual carry the certificate.
Round fractions back into decisions with a rule you can price. Rounding every variable at or above one half up to 1 keeps every edge covered while at most doubling the cost. A fractional optimum of 6 rounds to at most 12, so the rounding loses at most a factor of 2.
Write it linear, relax to fractions, certify with the dual, and round at a bounded price.
2 · Watch
Take it off screen
Where it sits
Learn first
This opens up
Nothing builds on it yet.
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.