--- title: "Approximation Ratios and How One Is Proved" description: "An approximation algorithm comes with a proved bound on how far its answer can sit from the best one, and the proof almost never mentions the optimum directly. It bounds the optimum from one side with" canonical: https://lightmysky.com/learn/computing/approximation-ratios-and-how-one-is-proved-mt_8pmBztDkFD source: https://lightmysky.com/learn/computing/approximation-ratios-and-how-one-is-proved-mt_8pmBztDkFD.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`. # Approximation Ratios and How One Is Proved An approximation algorithm comes with a proved bound on how far its answer can sit from the best one, and the proof almost never mentions the optimum directly. It bounds the optimum from one side with something computable, then bounds the algorithm against that. Subject: Computing · Area: Algorithms & Data Structures · Ages 22 to 23 Page: https://lightmysky.com/learn/computing/approximation-ratios-and-how-one-is-proved-mt_8pmBztDkFD ## Ready when they can - State what a ratio guarantees and what it says nothing about - Prove a ratio by comparing both the algorithm and the optimum to a computable bound - Give an instance where the bound is tight and say what that tightness means ## Lesson: Prove the bound without the optimum An approximation ratio is a proved worst-case promise, not a report on one run. For a minimization problem, factor 2 means the answer never exceeds twice the best possible. It says nothing about the typical gap, and nothing about what the optimum actually is. **Example.** The proof never touches the optimum directly. Find a computable middle bound B with the optimum on one side and your algorithm on the other: show the optimum is at least B, and your algorithm returns at most 2B. Chain them and your answer is at most twice optimal. Say B is 10 and you return 18: 18 sits below 20, so the ratio holds whatever the optimum is. A tight instance is one where the algorithm truly hits the bound, returning exactly twice the optimum. Tightness blesses the analysis, not the algorithm: it proves no smaller factor can be claimed for this method. It never means the method is bad, only that the proof is exact. **Tip.** To prove your own ratio, exhibit the middle bound first, then bound each side against it. Never try to compute the optimum, and never estimate the ratio from test data: one measured gap is an anecdote, not a proof. **Recap.** Sandwich a computable bound between the optimum and your answer to certify the factor. ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Living with NP-Hardness: Approximation and Heuristics](https://lightmysky.com/learn/computing/living-with-np-hardness-approximation-and-heuristics-mt_tZ82ty6h2u) - [Concentration Bounds and a High-Probability Guarantee](https://lightmysky.com/learn/computing/concentration-bounds-and-a-high-probability-guarantee-mt_WIltjK12oW) ## Opens up - [Linear Programming, Duality and Rounding](https://lightmysky.com/learn/computing/linear-programming-duality-and-rounding-mt_rsj6G8iydV)