Helpful context:

The Traveling Salesman Problem is NP-hard. Assuming P ≠ NP, you cannot find the optimal tour in polynomial time. But here is what you can do: find a tour that is at most 1.5 times optimal, in polynomial time, with a proof. This is Christofides' 1976 algorithm - one of the most elegant results in combinatorial optimization. It shows that you can give up optimality in a controlled, quantified way, and get efficiency in return.

Approximation algorithms make this trade precise. The optimality gap is not a bug; it is a feature, bounded by a proof.

The Approximation Ratio

An approximation algorithm doesn’t promise the best answer - it promises an answer within a provable factor of the best. A 2-approximation guarantees the result is at most twice the optimal. A 1.5-approximation guarantees it’s at most 1.5 times optimal. The factor is called the approximation ratio, and crucially, it must be proved - not just observed on examples.

Formally, an algorithm $A$ is an $\alpha$-approximation for a minimization problem if, for every instance $I$:

$$\text{ALG}(I) \leq \alpha \cdot \text{OPT}(I).$$

For maximization the inequality reverses: $\text{ALG}(I) \geq \text{OPT}(I) / \alpha$. The ratio $\alpha \geq 1$ is called the approximation ratio or approximation factor. An $\alpha$ of 1 means exact; the closer to 1, the better.

The proof of the ratio is as important as the algorithm itself. To prove $\text{ALG}(I) \leq \alpha \cdot \text{OPT}(I)$, you need a lower bound on $\text{OPT}(I)$ - some quantity you can compute that you know is at most the optimal value. Finding that lower bound is usually the creative step.

Vertex Cover: A 2-Approximation

A vertex cover is a set $S$ of vertices such that every edge has at least one endpoint in $S$. Finding the minimum vertex cover is NP-hard.

The algorithm. Find a maximal matching $M$ - greedily add non-adjacent edges until no more can be added. Return $S$ = both endpoints of every edge in $M$.

Why $S$ is a valid vertex cover. Every edge in $M$ is covered because we include both endpoints. Every edge not in $M$ is also covered: if edge $(u, v)$ is not in $M$, then $M$ is maximal, meaning either $u$ or $v$ was already matched - so at least one of them is in $S$.

The approximation ratio. We need to show $|S| \leq 2 \cdot \text{OPT}$.

The lower bound: any vertex cover must include at least one endpoint of each matching edge. Since the edges in $M$ are disjoint (it’s a matching), we need at least $|M|$ vertices in any cover. So $\text{OPT} \geq |M|$.

Our solution has $|S| = 2|M|$. Therefore $|S| = 2|M| \leq 2 \cdot \text{OPT}$.

This is a 2-approximation. It runs in $O(V + E)$.

You can also get a 2-approximation via LP rounding: solve the LP relaxation (which allows $x_v \in [0, 1]$), then round every $x_v \geq 1/2$ up to 1 and every $x_v < 1/2$ down to 0. Since the LP requires $x_u + x_v \geq 1$ for each edge, at least one endpoint must have $x \geq 1/2$ and thus gets rounded up, so every edge is covered. The cost at most doubles (we round up variables with $x \geq 1/2$), giving a 2-approximation. This LP-rounding argument is cleaner and generalizes more broadly.

Set Cover: Greedy $\ln n$-Approximation

Given a universe $U$ of $n$ elements and a collection of sets $S_1, \ldots, S_m \subseteq U$, find the fewest sets that cover $U$. This generalizes vertex cover.

The greedy algorithm. Repeat: pick the set $S_i$ covering the most currently uncovered elements. Stop when everything is covered.

The analysis. Let $\text{OPT} = k$ sets suffice for an optimal cover. We’ll track how many elements remain uncovered.

At any point, if $r$ elements remain, the $k$ optimal sets collectively cover all of them - so at least one set covers at least $r/k$ of the remaining elements (pigeonhole). The greedy algorithm picks this set (or better). After the first greedy pick, at most $n(1 - 1/k)$ elements remain. After the second, at most $n(1 - 1/k)^2$. After $t$ picks, at most $n(1 - 1/k)^t$.

Set $t = k \ln n$: the remaining count is at most $n \cdot (1 - 1/k)^{k \ln n} \leq n \cdot e^{-\ln n} = 1$. With at most 1 element uncovered, one more set finishes the job. So the greedy algorithm uses at most $k \ln n + 1 \approx \text{OPT} \cdot \ln n$ sets.

This $\ln n$-approximation is essentially best possible: unless P = NP, no polynomial-time algorithm achieves a $(1 - \epsilon) \ln n$ approximation for any $\epsilon > 0$. The hardness comes from the PCP theorem - the approximation complexity is tight.

Metric TSP: Christofides' 1.5-Approximation

In the metric TSP, cities satisfy the triangle inequality: $d(u, w) \leq d(u, v) + d(v, w)$. Find the shortest Hamiltonian cycle.

Christofides' algorithm (1976):

  1. Compute a minimum spanning tree $T$.
  2. Let $O$ be the set of odd-degree vertices in $T$. (There are an even number of them - the handshaking lemma.)
  3. Find a minimum-weight perfect matching $M$ on the vertices of $O$.
  4. Combine $T$ and $M$ to form a multigraph where every vertex has even degree.
  5. Find an Euler tour of this multigraph (possible because all degrees are even).
  6. Shortcut repeated vertices: whenever the tour revisits a city, skip it and go directly to the next unvisited city. By the triangle inequality, this doesn’t increase the total length.

The analysis. We need to bound the cost of $T$ and $M$ separately.

The MST cost: removing any single edge from the optimal TSP tour gives a spanning tree, so $\text{cost}(T) \leq \text{OPT}$.

The matching cost: consider the optimal tour restricted to the $|O|$ odd-degree vertices in order. This is a Hamiltonian cycle on those vertices. Partition it into two perfect matchings on $O$ (alternating edges). One of them costs at most half the tour cost on $O$, which is at most $\text{OPT}/2$. So $\text{cost}(M) \leq \text{OPT}/2$.

Total: $\text{ALG} \leq \text{cost}(T) + \text{cost}(M) \leq \text{OPT} + \text{OPT}/2 = 1.5 \cdot \text{OPT}$.

For 47 years, this 1.5 barrier stood. In 2020, Karlin, Klein, and Oveis Gharan announced an algorithm achieving $1.5 - \varepsilon$ for a tiny fixed $\varepsilon$, using a sophisticated randomized approach based on max-entropy distributions over spanning trees. The improvement was tiny in absolute terms, but enormous in principle: the first crack in a half-century-old bound.

Discomfort check. If an approximation ratio of 2 is so good, why can’t we always get $\alpha = 1 + \varepsilon$ for any $\varepsilon > 0$?

Some problems have inapproximability results: unless P = NP, you can’t get within a certain factor. Set cover cannot be approximated below $(1 - o(1)) \ln n$ - that’s tight. Max Clique cannot be approximated within $n^{1-\varepsilon}$ for any fixed $\varepsilon > 0$. Vertex cover cannot be approximated below $2 - \varepsilon$ under the Unique Games Conjecture. These hardness results come from the PCP theorem (Probabilistically Checkable Proofs) - a deep result saying that NP proofs can be verified by reading only a constant number of bits, which translates into hardness of approximation through gadget reductions. The approximation ratio is not just a feature of the algorithm; it is a property of the problem.

PTAS and FPTAS

A polynomial-time approximation scheme (PTAS) gives a $(1 + \varepsilon)$-approximation for any $\varepsilon > 0$, in time polynomial in $n$ (though possibly exponential in $1/\varepsilon$). The Euclidean TSP has a PTAS (Arora’s algorithm). Knapsack has a PTAS.

A fully polynomial-time approximation scheme (FPTAS) runs in time polynomial in both $n$ and $1/\varepsilon$. Knapsack has an FPTAS: scale all values by $K = \lfloor \varepsilon \cdot v_{\max} / n \rfloor$, run the exact DP on rounded values (now fast because max value is $O(n/\varepsilon)$), and the rounding loss is at most $\varepsilon \cdot \text{OPT}$.

Not everything has a PTAS. TSP without the triangle inequality cannot be approximated within any constant unless P = NP (if you could approximate it, you could solve Hamiltonian cycle). Max Clique has no PTAS unless P = NP.

Summary

Problem Best approximation ratio Hardness of approximation
Vertex cover 2 (LP rounding or matching) $2 - \varepsilon$ hard (UGC)
Set cover $\ln n$ (greedy) $(1-o(1))\ln n$ unless P = NP
Metric TSP $1.5$ (Christofides) NP-hard below $123/122$
Knapsack $1 + \varepsilon$ (FPTAS) Has FPTAS
Euclidean TSP $1 + \varepsilon$ (PTAS) Has PTAS
Max Clique $n^{1-\varepsilon}$ (trivial) Hard within $n^{1-\varepsilon}$

Approximation algorithms give you a controlled trade: polynomial time in exchange for a provable gap from optimal. The approximation ratio quantifies the gap. The inapproximability results tell you when you’ve reached the barrier. Between them, they tell you exactly how hard a problem is to solve approximately - which is often more useful than knowing it’s NP-hard.

Read next: