--- title: "Linear Programming, Duality and Rounding" description: "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 " canonical: https://lightmysky.com/learn/computing/linear-programming-duality-and-rounding-mt_rsj6G8iydV source: https://lightmysky.com/learn/computing/linear-programming-duality-and-rounding-mt_rsj6G8iydV.md retrieved: 2026-09-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Computing · Area: Algorithms & Data Structures · Ages 22 to 23 Page: https://lightmysky.com/learn/computing/linear-programming-duality-and-rounding-mt_rsj6G8iydV ## Ready when they can - 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 ## Lesson: Fractions first, decisions after 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. **Example.** 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. **Tip.** 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. **Recap.** Write it linear, relax to fractions, certify with the dual, and round at a bounded price. ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Matrix Multiplication and What It Represents](https://lightmysky.com/learn/mathematics/matrix-multiplication-and-what-it-represents-mt_0fJOMPlCxr) - [Approximation Ratios and How One Is Proved](https://lightmysky.com/learn/computing/approximation-ratios-and-how-one-is-proved-mt_8pmBztDkFD) - [Network Flow and the Max-Flow Min-Cut Theorem](https://lightmysky.com/learn/computing/network-flow-and-the-max-flow-min-cut-theorem-mt_momRV9lK1n)