You can't find the perfect delivery route in time, but you can guarantee your route is at most twice the ideal length. Approximation algorithms trade perfection for a proven promise — a bound on how far from best you could possibly be.
When optimal is out of reach
For NP-hard optimization problems, no known algorithm finds the exact optimum in polynomial time. Approximation algorithms instead run efficiently and return a solution provably within a bounded factor of optimal. That factor is the approximation ratio: a 2-approximation is guaranteed to be at most twice the optimal cost (for minimization).
Unlike a heuristic, an approximation algorithm comes with a proof that its output is within the stated ratio on every instance — trading exactness for a rigorous quality bound.
The classic greedy vertex-cover algorithm — repeatedly take both endpoints of an uncovered edge — is a 2-approximation: its cover is never more than twice the minimum.
- A minimization algorithm is a 1.5-approximation.
- The true optimum for an instance costs 100.
- State the worst-case cost the algorithm may return.
What you should see: A 1.5-approximation guarantees a cost of at most 1.5 × 100 = 150 on that instance, and never worse.