Approximation Algorithms — Mathematics Knowledge System

Overview

When a problem is NP-hard, insisting on the exact optimum is often infeasible at scale — so approximation algorithms trade a small, provable amount of solution quality for a guarantee of polynomial running time. An approximation algorithm comes with an approximation ratio: a proven bound on how far its output can be from the true optimum, in the worst case, over ALL inputs. This turns 'we can't solve this exactly, fast' into a precise, quantitative statement: 'we can always get within a factor of 2 of optimal, fast' (for example). Some NP-hard problems (like vertex cover and metric TSP) admit small constant-factor approximations; others (like general TSP without the triangle inequality) provably admit no bounded-factor approximation at all unless P = NP, and a few (the 'PTAS' problems) can be approximated arbitrarily closely at the cost of increasing runtime.

Intuition

Suppose you can't find the single cheapest way to cover all the edges of a graph with vertices (vertex cover is NP-hard), but you CAN quickly find a cover that's never worse than twice the cheapest possible. That's a huge practical win: instead of an algorithm that might take exponential time to find the perfect answer, you get an instant, provably-bounded-quality answer. The key discipline of approximation algorithms is proving the ratio holds for every possible input, not just typical ones — you need a mathematical argument (usually comparing your algorithm's output to some easy-to-compute lower bound on the true optimum, like a matching) that the guarantee never breaks, no matter how adversarial the input.

Formal Definition

Definition

For a minimization problem, an algorithm A is a ρ-approximation algorithm if, for every input instance I, it runs in polynomial time and its output ALG(I) is bounded relative to the true optimum OPT(I):

\text{ALG}(I) \le \rho \cdot \text{OPT}(I) \quad \text{for all instances } I \quad (\rho \ge 1, \text{ minimization})

Approximation ratio, minimization problems

\text{ALG}(I) \ge \rho \cdot \text{OPT}(I) \quad \text{for all instances } I \quad (0 < \rho \le 1, \text{ maximization})

Approximation ratio, maximization problems

\text{PTAS: } \forall \varepsilon > 0,\ \exists \text{ a } (1+\varepsilon)\text{-approximation algorithm running in time polynomial in } |I| \text{ (but not necessarily in } 1/\varepsilon)

Polynomial-time approximation scheme

Notation

Notation	Meaning
$\text{OPT}(I)$	The value of the true optimal solution to instance I
$\text{ALG}(I)$	The value of the solution produced by the approximation algorithm on I
$\rho$	The approximation ratio — the algorithm's worst-case guaranteed factor from optimal
$\text{PTAS}$	Polynomial-time approximation scheme: a family of algorithms achieving any fixed (1+ε) ratio

Theorems

Theorem 1: Vertex cover 2-approximation

\text{Taking both endpoints of every edge in any maximal matching yields a vertex cover of size} \le 2 \cdot \text{OPT}.

Theorem 2: Christofides' algorithm (metric TSP)

\text{For TSP instances satisfying the triangle inequality, Christofides' algorithm guarantees a tour of length} \le 1.5 \cdot \text{OPT}.

Theorem 3: Inapproximability of general TSP

\text{Without the triangle inequality, no polynomial-time algorithm can guarantee ANY constant approximation ratio for TSP, unless } P = NP.

Applications

Approximation algorithms with proven ratios are used in load balancing, facility location, and network design, where an NP-hard exact optimum is infeasible but a provably bounded-quality solution is required for service guarantees.

Worked Examples

The true minimum vertex cover for this path is {2, 4}: vertex 2 covers edges (1,2) and (2,3); vertex 4 covers edges (3,4) and (4,5). Every edge is covered, so OPT = 2.
$\text{OPT} = |\{2,4\}| = 2$
The matching {(1,2), (3,4)} is maximal (no edge can be added without sharing an endpoint with an existing matched edge: edge (2,3) shares vertex 2 or 3 with both matched edges). Taking both endpoints of each matched edge gives the cover {1,2,3,4}.
$\text{ALG} = |\{1,2,3,4\}| = 4$
Check the ratio: ALG / OPT = 4 / 2 = 2, matching the algorithm's guaranteed worst-case bound of exactly 2.
$\frac{\text{ALG}}{\text{OPT}} = \frac{4}{2} = 2 \le 2 \cdot \text{OPT}$

Answer: ALG = 4 and OPT = 2, giving a ratio of exactly 2 — consistent with (and tight for) the general 2-approximation guarantee: taking both endpoints of a maximal matching never exceeds twice the true minimum vertex cover.

Practice Problems

Difficulty 6/10

Why does taking BOTH endpoints of every edge in a maximal matching (rather than just one, cleverly chosen, endpoint) give a provable approximation guarantee for vertex cover?

Difficulty 7/10

A logistics company has a delivery network satisfying the triangle inequality (direct routes are never longer than routes through a third stop) and wants a tour of all 50 delivery points. If Christofides' algorithm returns a tour of length 180, what is the largest possible value of the true optimal tour length, and the smallest?

Difficulty 5/10

A ρ-approximation algorithm for a minimization NP-hard problem guarantees that its solution is:

Always exactly optimalAt most ρ times the true optimum, for every input, and runs in polynomial timeCorrect only on average-case inputsOptimal only when ρ = 1

Common Mistakes

Common Mistake

Believing an approximation ratio is a statement about average performance on typical inputs.

An approximation ratio is a WORST-CASE guarantee: it must hold for every possible input instance, including adversarially constructed ones, not just 'typical' or 'random' ones. This is what makes it a mathematically provable guarantee rather than an empirical observation.

Common Mistake

Assuming every NP-hard optimization problem admits a good (small constant-factor) approximation algorithm.

Some NP-hard problems provably admit NO bounded-ratio polynomial-time approximation at all unless P = NP (e.g. general TSP without the triangle inequality, or maximum clique within any constant factor) — approximability itself varies enormously and must be established or refuted problem by problem.

Quiz

Flashcards

1 / 4

Historical Background

The systematic study of approximation algorithms grew directly out of 1970s NP-completeness theory: once Cook, Levin, and Karp established that huge classes of optimization problems have no known efficient exact algorithms, researchers began asking how CLOSE to optimal a polynomial-time algorithm could provably get. Nicos Christofides's 1976 algorithm for the metric Traveling Salesman Problem, guaranteeing a solution within 1.5x optimal, became a landmark early result. David Johnson's 1974 work formalized approximation ratios for problems like set cover and graph coloring, and the field matured further in the 1990s with the PCP theorem, which supplied the tools to prove HARDNESS of approximation — showing that for some problems, no algorithm can even get close to optimal in polynomial time unless P = NP.

1974
David Johnson formalizes worst-case approximation ratios for several NP-hard optimization problems
David S. Johnson
1976
Nicos Christofides publishes a 1.5-approximation algorithm for metric TSP
Nicos Christofides
1992
The PCP theorem enables proofs of hardness of approximation for many NP-hard problems
Sanjeev Arora, others

Summary

Approximation algorithms trade a proven, bounded loss in solution quality for guaranteed polynomial running time on NP-hard problems.
The approximation ratio ρ must hold for every input in the worst case, not merely on average.
Vertex cover has a simple 2-approximation via maximal matching; metric TSP has Christofides' 1.5-approximation.
Not every NP-hard problem is approximable to within a constant factor — inapproximability results (often via the PCP theorem) prove some problems resist even approximate polynomial-time solutions unless P = NP.

References

WebsiteWikipedia — Approximation algorithm
WebsiteWikipedia — Christofides algorithm
WebsiteWikipedia — Vertex cover