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.
What a learner can do afterwards
- 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
1 · Read
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.
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.
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.
Sandwich a computable bound between the optimum and your answer to certify the factor.
2 · Watch
Take it off screen
Where it sits
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.