JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

The Approximation Ratio

When a problem is NP-hard, demanding the exact optimum can cost exponential time — so we settle for a solution provably close to it. The approximation ratio is the number that pins down exactly how close "close" is, and this guide builds it carefully and honestly.

What to do when exact is too expensive

You arrive at this rung carrying a piece of bad news from the last one. Once a problem is shown to be NP-hard, nobody on Earth knows a polynomial-time algorithm that always returns the exact optimum, and — because P versus NP is open — nobody has proven one cannot exist either. So for a genuinely NP-hard problem like vertex cover or the travelling salesman, three honest roads are open. You can demand the exact optimum and pay possibly exponential time. You can run a fast heuristic and hope it does well, with no promise at all. Or you can take the middle road this whole rung is about: run a fast algorithm that comes with a provable guarantee of how far from optimal its answer can ever be.

That third road is what an approximation algorithm does. It runs in polynomial time, and it carries a theorem that bounds the quality of its output against the unknown optimum. Notice the contrast with a plain heuristic: a heuristic might be excellent in practice yet give you nothing you can prove, whereas an approximation algorithm trades a little solution quality for a guarantee you can write down and trust for every input. The number that records the strength of that guarantee is the approximation ratio, and getting it exactly right — including its sign conventions and its honest limits — is the job of this first guide.

Defining the ratio without seeing the optimum

Here is the central trick, and it is worth slowing down for: the definition compares your answer to an optimum you cannot compute. Let OPT be the value (cost or profit) of a true optimal solution for a given instance, and let ALG be the value your algorithm returns on that same instance. For a minimization problem (vertex cover wants the fewest vertices, TSP wants the shortest tour) we say the algorithm is a c-approximation if ALG <= c times OPT for every instance, where c >= 1. A 2-approximation therefore promises ALG is never more than twice the smallest possible — at most double the cost, never worse. The closer c is to 1, the tighter the promise; c = 1 would mean exact.

For a maximization problem (knapsack wants the most value, max-cut wants the most cut edges) the inequality flips: an algorithm is a c-approximation if ALG >= c times OPT for every instance, with 0 < c <= 1. A (1/2)-approximation for a maximization problem guarantees you collect at least half the optimal value. Conventions differ between textbooks — some write the maximization ratio as OPT/ALG >= some number >= 1 so that "bigger ratio = worse" matches the minimization side — so always check which way a source points the inequality. The substance is identical; only the bookkeeping flips.

The deep puzzle: how do you bound against an unknown OPT?

Stop and feel the difficulty. To prove ALG <= 2 times OPT you seem to need OPT — but computing OPT is the very NP-hard problem you gave up on. The escape, and the single most important idea in approximation, is the lower bound on OPT (for maximization, an upper bound). You find some quantity L that you can compute cheaply and that you can prove satisfies L <= OPT, however the optimum turns out. Then you show your algorithm's output satisfies ALG <= 2 times L. Chaining these gives ALG <= 2L <= 2 times OPT, and OPT itself never had to be computed — it was squeezed between two things you control.

The classic illustration is the 2-approximation for vertex cover, which the next guide unfolds in full; here just see the shape of the argument. The algorithm repeatedly picks any uncovered edge and grabs both its endpoints. The edges it picks form a matching — no two share a vertex — and any valid vertex cover must include at least one endpoint of each matched edge, so OPT >= (number of matched edges). That inequality is your computable lower bound L. Meanwhile the algorithm took exactly 2 endpoints per matched edge, so ALG = 2 times (matched edges) = 2L <= 2 times OPT. The matching is the scaffold: it is something we can see and count, and it pins OPT from below without our ever finding OPT.

want to prove:   ALG  <=  c * OPT     (minimization)

but OPT is NP-hard to compute, so instead:
  1. build a cheap, computable L  with  L <= OPT   (a lower bound on OPT)
  2. relate the algorithm to L:        ALG <= c * L
  3. chain them:               ALG <= c*L <= c * OPT     done.

(maximization: build a cheap U with OPT <= U, show ALG >= c*U)
The universal template: every approximation proof finds a computable surrogate for OPT and squeezes the unknown optimum between it and the algorithm's output.

Why the ratio is more honest than "it usually works"

You already met an algorithm with no such guarantee. Greedy on the 0/1 knapsack — take items by best value-per-weight — looks sensible and is often fine, but it can be made arbitrarily bad: a single heavy, hugely valuable item the greedy skips can leave it with a tiny fraction of OPT. "Looks locally best" was never a proof, and here it has no worst-case factor at all. That is precisely the gap an approximation ratio closes. It forces you to confront the adversary's nastiest instance and either bound it or admit you cannot.

Two honesty checks keep the ratio from being oversold. First, a c-approximation is a worst-case ceiling, not a forecast — the bound 2 says "never worse than double," it does not say "about double." Many 2-approximations return the exact optimum on most natural inputs. Second, the ratio can be tight: there is often an explicit family of instances that drives ALG/OPT right up to c, proving the analysis cannot be improved for that algorithm. A tight 2 means some input really does cost twice optimal; a merely proven 2 might secretly be better but unanalysed. Knowing which you have matters when you choose between competing methods.

A field of guarantees, and the road through this rung

Not every problem yields a constant ratio, and the variety is part of what makes the field rich. Some problems admit a fixed constant: vertex cover gets 2, and metric TSP gets 2 by a spanning-tree argument and then 1.5 by Christofides, the subject of a guide ahead. Some admit only a growing ratio: greedy set cover achieves a ratio of about ln n, and — strikingly — that is essentially the best any polynomial algorithm can do unless P = NP. And some problems are inapproximable: for general (non-metric) TSP, even a constant-factor approximation would let you solve an NP-complete problem, so none exists unless P = NP. The ratio is not a free dial; how small it can be is itself a deep, problem-specific theorem.

  1. Guide 2 builds the greedy and combinatorial approximations from scratch — the vertex-cover matching argument in full, and greedy set cover's ln n ratio with its tight example.
  2. Guide 3 takes on metric TSP: why the triangle inequality is what makes it approximable, the spanning-tree 2-approximation, and Christofides' clever 1.5.
  3. Guide 4 introduces linear-programming relaxation and rounding — solve a fractional relaxation in polynomial time, then round it back to an integer solution while bounding the loss.
  4. Guide 5 reaches the strongest guarantees, PTAS and FPTAS: families of algorithms that achieve ratio 1 + epsilon for any epsilon you choose, trading more time for more accuracy.

Throughout, hold onto the one idea this guide installed: an approximation algorithm is a polynomial-time procedure shipped with a worst-case proof, and that proof almost always works by inventing a computable surrogate that traps OPT from one side. Every technique to come — combinatorial, LP-based, or scheme-based — is a different, more powerful way to build that surrogate and tighten the squeeze. Keep your eye on where each proof finds its bound on OPT, and the whole rung will read as variations on a single, honest theme.