---
title: Approximation Algorithms
module: Intractability
moduleNumber: 12
lessonNumber: 4
order: 1204
summary: |
  When a problem is $\mathsf{NP}$-hard we can still ask for a solution
  provably close to optimal. This lesson makes the approximation ratio
  $\rho$ precise, separates absolute from relative guarantees, and proves the
  ratios of four classic algorithms: greedy set cover ($H_n \approx \ln n$),
  the MST-doubling $2$-approximation for metric TSP, load balancing, and the
  knapsack FPTAS. It closes with the hierarchy PTAS / FPTAS and the limits of
  inapproximability.
topics: [Approximation, NP-Completeness]
sources:
  - book: CLRS
    ref: "Ch. 35 — Approximation Algorithms"
  - book: Skiena
    ref: "§11.10 — Approximation Algorithms"
  - book: Erickson
    ref: "Ch. 12 — NP-Hardness; Approximation"
practice:
  - title: 'Set Cover'
    slug: set-cover
    difficulty: Hard
  - title: 'Maximum Units on a Truck'
    slug: maximum-units-on-a-truck
    difficulty: Easy
  - title: 'Last Stone Weight II'
    slug: last-stone-weight-ii
    difficulty: Medium
  - title: 'Find Minimum Time to Finish All Jobs'
    slug: find-minimum-time-to-finish-all-jobs
    difficulty: Hard
---

The previous lesson, [Coping with NP-Hardness](/algorithms/intractability/coping-with-hardness),
surveyed four honest responses to a problem we cannot solve exactly and quickly:
approximate, use heuristics, pay for a smart exponential search, or exploit special
structure. It worked the first response through a single example, the
$2$-approximation for vertex cover. This lesson develops that response in
detail. We define the **approximation ratio** with care, separate two
flavors of guarantee, and then prove ratios for a sequence of canonical algorithms,
each illustrating a different proof technique. We finish by classifying
which problems can be approximated _arbitrarily_ well, and which cannot be
approximated at all.

The recurring move, established last time, is worth restating because every proof
below is a variation on it: we bound our output not against the optimum $C^{\ast}$,
which we cannot compute, but against a **surrogate** quantity, a lower bound for a
minimization (or an upper bound for a maximization) that we _can_ reason about.
Most of approximation analysis is finding the right surrogate.

## What "approximate" means precisely

Fix an optimization problem. On an instance $I$, let $\mathrm{OPT}(I)$ be the cost
of an optimal solution and $A(I)$ the cost of the solution our algorithm $A$
returns. There are two distinct ways to say "$A$ is close to optimal," and
conflating them causes endless confusion.

> **Definition (Absolute vs. relative approximation).**
>
> - $A$ is an **absolute approximation** with error $k$ if
>   $|A(I) - \mathrm{OPT}(I)| \le k$ for every instance $I$, with $k$ a constant
>   independent of the input.
> - $A$ is a **relative ($\rho$-)approximation** if its cost is within a
>   _multiplicative_ factor $\rho$ of optimal on every instance.

Absolute guarantees are rare: most $\mathsf{NP}$-hard problems
**scale**, so an additive error that holds on small instances cannot hold on large
ones. (If you could always come within $k$ of the optimal graph coloring, you could
take $k+1$ disjoint copies of an instance and divide out the additive slack to solve
it exactly.) So the relative ratio is the standard guarantee, and we pin it down
exactly.

> **Definition ($\rho$-approximation).** For a **minimization** problem, $A$ is a
> $\rho$-approximation (with $\rho \ge 1$) if it runs in polynomial time and, on
> every instance, returns a feasible solution of cost
> $$ A(I) \le \rho \cdot \mathrm{OPT}(I). $$
> For a **maximization** problem the bound flips: $A(I) \ge \mathrm{OPT}(I) / \rho$
> (equivalently $A(I) \ge \alpha \cdot \mathrm{OPT}(I)$ with $\alpha = 1/\rho \le 1$).
> The number $\rho$ is the **approximation ratio**; an algorithm achieving it is a
> $\rho$-**approximation algorithm**.

Two conventions are in use. Some authors quote the maximization ratio as a
fraction $\alpha \le 1$ (a "$\tfrac12$-approximation" returns at least half of
optimal); others keep $\rho \ge 1$ throughout. They say the same thing; we will use
$\rho \ge 1$ for minimization and the fraction $\alpha \le 1$ for maximization, and
state which we mean each time.

A ratio may be a constant ($2$ for vertex cover), may **grow with the input**
($\Theta(\log n)$ for set cover, as we are about to prove), or may be tunable to any
value above $1$ at the cost of running time (an approximation _scheme_). The last
section organizes these into a hierarchy.

## Greedy set cover: a logarithmic ratio

Our first proof gives a ratio that is _not_ constant — it grows like the logarithm
of the input — and it introduces the **charging argument**, where we account for
the algorithm's cost by distributing it onto the elements it serves.

> **Definition (Set Cover).** Given a universe $U$ of $n$ elements and a family
> $\mathcal{F} = \{S_1, \dots, S_m\}$ of subsets whose union is $U$, find a
> minimum-size subfamily $\mathcal{C} \subseteq \mathcal{F}$ whose union is still
> all of $U$.

Set cover is $\mathsf{NP}$-hard, and it is the abstract form of many
resource-selection problems: pick the fewest cell towers covering every
neighborhood, the fewest tests catching every fault, the fewest committees spanning
every skill. The natural greedy rule is simple: **repeatedly take the
set that covers the most still-uncovered elements.**[^clrs-setcover]

```algorithm
caption: $\textsc{Greedy-Set-Cover}(U, \mathcal{F})$ — repeatedly grab the largest uncovered set
number: 1
$\mathcal{C} \gets \emptyset$
$R \gets U$ // elements still uncovered
while $R \neq \emptyset$ do
  pick $S \in \mathcal{F}$ maximizing $|S \cap R|$ // most new coverage
  $\mathcal{C} \gets \mathcal{C} \cup \{S\}$
  $R \gets R \setminus S$ // remove newly covered elements
return $\mathcal{C}$
```

Each iteration covers at least one new element, so the loop runs at most $n$ times;
finding the best set is polynomial, so the whole algorithm is. The figure shows the
first greedy choice: among the available sets, the one covering the largest part
of the uncovered universe wins.

$$
% caption: One step of $\textsc{Greedy-Set-Cover}$: among candidate sets, pick the one
%          covering the most still-uncovered elements (here $S_1$ with $4$ vs.
%          $3$ and $2$).
\begin{tikzpicture}[font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % universe elements laid out in a grid
  \foreach \x in {0,1,2,3,4,5} {
    \foreach \y in {0,1} {
      \node[circle, draw, fill=black!7, inner sep=2.4pt] (e\x\y) at (\x*1.05, \y*1.0) {};
    }
  }
  % S1: largest set (4 elements), drawn as a green rounded box -- the pick
  \draw[green, very thick]
    (-0.36,-0.34) rectangle (3.36,0.34);
  \node[anchor=north, font=\scriptsize, text=green] at (1.5,-0.46) {$S_1$ covers $4$, chosen};
  % S2: 3 elements on the top row
  \draw[acc, thick, dashed]
    (1.64,0.66) rectangle (4.36,1.34);
  \node[anchor=south, font=\scriptsize, text=acc] at (3.0,1.46) {$S_2$ covers $3$};
  % S3: 2 elements far right
  \draw[acc, thick, dashed]
    (4.64,-0.34) rectangle (5.36,1.34);
  \node[anchor=west, font=\scriptsize, text=acc] at (5.5,0.5) {$S_3$ covers $2$};
\end{tikzpicture}
$$

$$
% caption: Greedy run over three rounds: each round grabs the set covering the most
%          still-uncovered elements (green = covered so far), until the universe is full
\begin{tikzpicture}[font=\small, x=8.5mm, y=8.5mm]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % three snapshots stacked, 8 elements each, covered set grows
  % round labels and which indices are covered cumulatively
  \foreach \row/\lbl/\cov in {%
    2/{round 1: take set of 4}/{0,1,2,3},
    1/{round 2: add set of 3}/{0,1,2,3,4,5,6},
    0/{round 3: add set of 1}/{0,1,2,3,4,5,6,7}} {
    \node[anchor=east, font=\scriptsize] at (-0.7, \row*1.5) {\lbl};
    \foreach \i in {0,1,2,3,4,5,6,7} {
      \node[circle, draw=black, fill=black!7, inner sep=2.2pt] (n\row\i) at (\i, \row*1.5) {};
    }
    \foreach \i in \cov {
      \node[circle, draw=green, fill=green!22, inner sep=2.2pt] at (\i, \row*1.5) {};
    }
  }
  % highlight the freshly chosen set in each round with an acc bracket
  \draw[acc, thick] (-0.34,2*1.5-0.34) rectangle (3.34,2*1.5+0.34);
  \draw[acc, thick] (3.66,1*1.5-0.34) rectangle (6.34,1*1.5+0.34);
  \draw[acc, thick] (6.66,0*1.5-0.34) rectangle (7.34,0*1.5+0.34);
  \node[anchor=west, font=\scriptsize, text=green] at (7.7, 0) {all covered};
\end{tikzpicture}
$$

Greedy can use more sets than necessary, and the worst case is genuinely
logarithmic. The classic bad instance is a universe of $2^{k}-1$ elements that the
optimum covers with two sets, but greedy peels off in $k$ steps, each grabbing
barely more than half of what remains. The precise bound uses the **harmonic
number** $H_n = 1 + \tfrac12 + \tfrac13 + \dots + \tfrac1n$.

> **Theorem (Greedy ratio).** $\textsc{Greedy-Set-Cover}$ is an $H_n$-approximation,
> where $n = |U|$. Since $H_n \le \ln n + 1$, it returns at most
> $(\ln n + 1)\,\mathrm{OPT}$ sets.

> **Proof.** Charge the cost by spreading each chosen set's "price" of $1$ over the
> elements it newly covers. When greedy picks a set $S$ that covers $t$ previously
> uncovered elements, assign to each of those $t$ elements the cost
> $$ c(e) = \frac{1}{t}. $$
> Every element receives exactly one charge, at the moment it is first covered, and
> the total cost of greedy's cover is $|\mathcal{C}| = \sum_{e \in U} c(e)$.
>
> Now bound the charges accumulated _inside one optimal set_. Fix any
> $S^{\ast} \in \mathcal{F}$ from an optimal solution, with $|S^{\ast}| = s$. List its
> elements $e_1, \dots, e_s$ in the order greedy covers them. Consider the moment
> just before $e_i$ is covered: at least the $s - i + 1$ elements
> $e_i, \dots, e_s$ of $S^{\ast}$ are still uncovered. So $S^{\ast}$ itself would cover at
> least $s - i + 1$ new elements — and greedy chose a set covering _at least as
> many_. Hence the set greedy actually picked covered $t \ge s - i + 1$ new
> elements, so
> $$ c(e_i) = \frac{1}{t} \le \frac{1}{s - i + 1}. $$
> Summing over $S^{\ast}$,
> $$
>   \sum_{e \in S^{\ast}} c(e) \;\le\; \sum_{i=1}^{s} \frac{1}{s-i+1}
>     \;=\; \frac{1}{s} + \frac{1}{s-1} + \dots + 1 \;=\; H_s \;\le\; H_n.
> $$
> Let $\mathcal{C}^{\ast}$ be an optimal cover. Every element lies in some set of
> $\mathcal{C}^{\ast}$, so summing the per-set bound over those $\mathrm{OPT}$ sets
> covers every element's charge at least once:
> $$
>   |\mathcal{C}| = \sum_{e \in U} c(e)
>     \;\le\; \sum_{S^{\ast} \in \mathcal{C}^{\ast}} \sum_{e \in S^{\ast}} c(e)
>     \;\le\; \sum_{S^{\ast} \in \mathcal{C}^{\ast}} H_n
>     \;=\; H_n \cdot \mathrm{OPT}.
> $$
> Thus $|\mathcal{C}| \le H_n \cdot \mathrm{OPT} \le (\ln n + 1)\,\mathrm{OPT}$.
> $\qed$

The logarithmic factor is not an artifact of the analysis: greedy is essentially
optimal here. A deep result shows that, unless $\mathsf{P} = \mathsf{NP}$, **no**
polynomial-time algorithm approximates set cover within $(1 - o(1))\ln n$.[^lund-yannakakis]
Greedy is the best we can hope for, up to lower-order terms.

::impl{algo="greedy_set_cover"}

## Metric TSP: the MST-doubling 2-approximation

The traveling-salesman problem asks for a minimum-cost cycle visiting every vertex
once. In full generality it admits no constant-factor approximation
(established at the end of this lesson). But almost every TSP that arises from
geography or physical distance satisfies the **triangle inequality**,
$c(u,w) \le c(u,v) + c(v,w)$ — going direct is never longer than detouring through
a third point. This **metric** case admits a $2$-approximation built
on the [minimum spanning tree](/algorithms/graphs/minimum-spanning-trees).[^clrs-tsp]

The coping lesson sketched this construction; here we develop it in full and prove
the ratio. The whole idea fits in one line: an MST is a cheap connected backbone,
and a tour is just a connected backbone with the extra demand of being a single
cycle, so the tour cannot cost much more than the tree.

```algorithm
caption: $\textsc{MST-TSP}(G, c)$ — metric TSP tour within $2\times$ optimal
number: 2
$T \gets$ minimum spanning tree of $G$ // e.g. Prim or Kruskal
pick any vertex $r$ as root
$L \gets$ vertices in the order first visited by a preorder walk of $T$ from $r$
return the cycle that visits the vertices in the order $L$, then closes back to $r$
```

The algorithm never literally doubles edges; the preorder walk is the clean way to
realize the "double then shortcut" intuition. Doubling each tree edge makes every
degree even, so an **Euler tour** exists that traverses every (doubled) edge once
and has cost exactly $2\,c(T)$. Walking that Euler tour and **skipping** vertices
already seen yields precisely the preorder sequence $L$. The figure shows both
halves: the MST backbone, then the shortcut Hamiltonian cycle.

$$
% caption: Metric-TSP $2$-approximation. Left: MST $T$ (cost $\le \mathrm{OPT}$).
%          Right: shortcut the doubled Euler walk into a Hamiltonian cycle of cost
%          $\le 2\,c(T) \le 2\,\mathrm{OPT}$.
\begin{tikzpicture}[font=\small,
    v/.style={circle, draw, fill=black!7, inner sep=1.8pt, minimum size=6mm}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % left: MST
  \begin{scope}
    \node[v] (a) at (0,2.2)   {$a$};
    \node[v] (b) at (1.9,2.6)  {$b$};
    \node[v] (c) at (1.4,0.9)  {$c$};
    \node[v] (d) at (3.2,1.4)  {$d$};
    \node[v] (e) at (0.3,0.5)  {$e$};
    \draw[green, very thick] (a)--(b);
    \draw[green, very thick] (a)--(c);
    \draw[green, very thick] (c)--(d);
    \draw[green, very thick] (a)--(e);
    \node[anchor=north, font=\scriptsize, text=green] at (1.6,-0.05)
      {MST: cost at most OPT};
  \end{scope}
  % arrow with two-line annotation
  \draw[->, thick] (3.9,1.4) -- node[above, font=\scriptsize]{double} node[below, font=\scriptsize]{shortcut} (5.6,1.4);
  % right: shortcut Hamiltonian cycle a-b-c-d-e-a
  % right: shortcut Hamiltonian cycle a-b-c-d-e-a, nodes placed as a convex pentagon
  \begin{scope}[shift={(6.4,0)}]
    \node[v] (a) at (0.0,1.5)  {$a$};
    \node[v] (b) at (1.3,2.7)  {$b$};
    \node[v] (c) at (3.0,2.0)  {$c$};
    \node[v] (d) at (2.9,0.6)  {$d$};
    \node[v] (e) at (1.1,-0.1) {$e$};
    \draw[acc, very thick] (a)--(b);
    \draw[acc, very thick] (b)--(c);
    \draw[acc, very thick] (c)--(d);
    \draw[acc, very thick] (d)--(e);
    \draw[acc, very thick] (e)--(a);
    \node[anchor=north, font=\scriptsize, text=acc] at (1.5,-0.4)
      {tour: cost at most twice OPT};
  \end{scope}
\end{tikzpicture}
$$

$$
% caption: Doubling each MST edge makes every degree even, so an Euler walk traverses all
%          edges at cost $2\,c(T)$; shortcutting past repeats yields the tour
\begin{tikzpicture}[font=\small,
    v/.style={circle, draw, fill=black!7, inner sep=1.8pt, minimum size=6mm}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  \node[v] (a) at (0,2.2)   {$a$};
  \node[v] (b) at (1.9,2.6)  {$b$};
  \node[v] (c) at (1.4,0.9)  {$c$};
  \node[v] (d) at (3.2,1.4)  {$d$};
  \node[v] (e) at (0.3,0.5)  {$e$};
  % each tree edge drawn as two slightly offset parallel strokes = doubled;
  % shorten both ends so strokes stop at the node rim, clear of the letters
  \draw[green, thick, shorten >=7pt, shorten <=7pt] ([yshift=1.2pt]a.center)--([yshift=1.2pt]b.center);
  \draw[green, thick, shorten >=7pt, shorten <=7pt] ([yshift=-1.2pt]a.center)--([yshift=-1.2pt]b.center);
  \draw[green, thick, shorten >=7pt, shorten <=7pt] ([xshift=1.2pt]a.center)--([xshift=1.2pt]c.center);
  \draw[green, thick, shorten >=7pt, shorten <=7pt] ([xshift=-1.2pt]a.center)--([xshift=-1.2pt]c.center);
  \draw[green, thick, shorten >=7pt, shorten <=7pt] ([yshift=1.2pt]c.center)--([yshift=1.2pt]d.center);
  \draw[green, thick, shorten >=7pt, shorten <=7pt] ([yshift=-1.2pt]c.center)--([yshift=-1.2pt]d.center);
  \draw[green, thick, shorten >=7pt, shorten <=7pt] ([xshift=1.2pt]a.center)--([xshift=1.2pt]e.center);
  \draw[green, thick, shorten >=7pt, shorten <=7pt] ([xshift=-1.2pt]a.center)--([xshift=-1.2pt]e.center);
  \node[anchor=north, font=\scriptsize, text=green] at (1.6,-0.05)
    {doubled tree: cost is twice c of T};
  % an Euler-walk order annotation
  \node[anchor=west, font=\scriptsize, text=acc] at (3.6,1.9)
    {Euler walk visits};
  \node[anchor=west, font=\scriptsize, text=acc] at (3.6,1.35)
    {every edge once};
  \node[anchor=west, font=\scriptsize, text=acc] at (3.6,0.55)
    {shortcut past};
  \node[anchor=west, font=\scriptsize, text=acc] at (3.6,0.0)
    {repeated vertices};
\end{tikzpicture}
$$

> **Theorem (Metric-TSP ratio).** On any instance obeying the triangle inequality,
> $\textsc{MST-TSP}$ returns a tour of cost at most $2\,\mathrm{OPT}$.

> **Proof.** Two inequalities chain together.
>
> _The tree under-bounds the optimum._ Take an optimal tour and delete one of its
> edges. What remains is a path through all $n$ vertices, which is in particular a
> spanning tree. Since $T$ is a _minimum_ spanning tree, $c(T)$ is no larger than
> this path, which is no larger than the whole optimal tour:
> $$ c(T) \le \mathrm{OPT}. $$
>
> _The tour over-bounds by at most the doubled tree._ The full walk $W$ that
> traverses each edge of $T$ twice (down into a subtree and back up) visits every
> vertex and has cost
> $$ c(W) = 2\,c(T). $$
> Our returned cycle is obtained from $W$ by **shortcutting**: whenever $W$ would
> revisit an already-seen vertex, we instead jump directly to the next unvisited
> one. By the triangle inequality each such shortcut replaces a two-hop detour
> $u \to v \to w$ by the direct edge $u \to w$ with $c(u,w) \le c(u,v) + c(v,w)$,
> so shortcutting **never increases** cost. Hence the tour costs at most
> $c(W) = 2\,c(T)$.
>
> Combining, $\text{tour} \le 2\,c(T) \le 2\,\mathrm{OPT}$. $\qed$

Both inequalities are tight in isolation, so $2$ is the honest guarantee for this
particular algorithm. It is **not** the best ratio known: **Christofides'
algorithm** replaces the wasteful doubling with a cleverer parity fix. Instead of
duplicating _every_ tree edge, it adds a minimum-weight **perfect matching** on
just the odd-degree vertices of $T$ — the only vertices whose degree blocks an
Euler tour. That matching costs at most $\tfrac12\,\mathrm{OPT}$, and the same
shortcutting argument then yields a tour of cost at most
$c(T) + \tfrac12\,\mathrm{OPT} \le \tfrac32\,\mathrm{OPT}$.[^christofides] For decades
the resulting $\tfrac32$ was the best constant known for metric TSP.

::impl{algo="mst_tsp"}

## Load balancing: a second 2-approximation, by averaging

To show a different surrogate at work, consider **makespan scheduling**: assign
$n$ jobs with processing times $p_1, \dots, p_n$ to $m$ identical machines so as to
minimize the **makespan**, the finishing time of the busiest machine. Deciding the
optimum is $\mathsf{NP}$-hard. The **list-scheduling** greedy assigns each job, in
turn, to whichever machine is currently least loaded.

```algorithm
caption: $\textsc{List-Schedule}(p_1 \dots p_n, m)$ — greedy makespan within $2\times$ optimal
number: 3
$\text{load}[1 \dots m] \gets 0$ // current load of each machine
for $j \gets 1$ to $n$ do
  $i \gets \arg\min_{k} \text{load}[k]$ // least-loaded machine
  assign job $j$ to machine $i$
  $\text{load}[i] \gets \text{load}[i] + p_j$
return the assignment
```

$$
% caption: List-scheduling on $m = 3$ machines: each job (a bar of height $p_j$) lands on
%          the currently shortest stack; the tallest stack is the makespan
\begin{tikzpicture}[font=\small, x=10mm, y=5mm]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % three machine stacks; each block annotated by job processing time
  % machine 1: 3 then 2 then 1 (total 6) -- the busiest = makespan
  \fill[acc!12] (0,0) rectangle (0.9,3);    \draw (0,0) rectangle (0.9,3);
  \fill[acc!20] (0,3) rectangle (0.9,5);    \draw (0,3) rectangle (0.9,5);
  \fill[acc!28] (0,5) rectangle (0.9,6);    \draw (0,5) rectangle (0.9,6);
  % machine 2: 4 then 1 (total 5)
  \fill[acc!12] (1.7,0) rectangle (2.6,4);  \draw (1.7,0) rectangle (2.6,4);
  \fill[acc!20] (1.7,4) rectangle (2.6,5);  \draw (1.7,4) rectangle (2.6,5);
  % machine 3: 2 then 3 (total 5)
  \fill[acc!12] (3.4,0) rectangle (4.3,2);  \draw (3.4,0) rectangle (4.3,2);
  \fill[acc!20] (3.4,2) rectangle (4.3,5);  \draw (3.4,2) rectangle (4.3,5);
  % baseline
  \draw[thick] (-0.2,0) -- (4.6,0);
  \node[font=\scriptsize, anchor=north] at (0.45,-0.3) {machine 1};
  \node[font=\scriptsize, anchor=north] at (2.15,-0.3) {machine 2};
  \node[font=\scriptsize, anchor=north] at (3.85,-0.3) {machine 3};
  % makespan marker on the tallest stack (machine 1)
  \draw[green, very thick, dashed] (-0.45,6) -- (4.7,6);
  \node[font=\scriptsize, text=green, anchor=west] at (4.8,6) {makespan};
  \node[font=\scriptsize, text=acc, anchor=west] at (4.8,2.7) {busiest stack};
\end{tikzpicture}
$$

This greedy needs only two facts that lower-bound _any_
schedule, including the optimum.

> **Theorem (List-scheduling ratio).** $\textsc{List-Schedule}$ produces a makespan
> at most $2\,\mathrm{OPT}$.

> **Proof.** Two unavoidable lower bounds on the optimal makespan $\mathrm{OPT}$:
>
> - **Average load.** The total work $\sum_j p_j$ is split over $m$ machines, so
>   some machine does at least the average: $\mathrm{OPT} \ge \tfrac1m \sum_j p_j$.
> - **Biggest job.** Some machine must run the longest job whole:
>   $\mathrm{OPT} \ge \max_j p_j$.
>
> Now examine greedy's busiest machine $i$, and let job $\ell$ be the _last_ one it
> received, with processing time $p_\ell$. At the moment greedy placed $\ell$ on
> $i$, machine $i$ was the least loaded, so its load-before-$\ell$, call it $D$, was
> no more than every machine's load — hence no more than the average load,
> $D \le \tfrac1m \sum_j p_j \le \mathrm{OPT}$. The machine's final load is
> $$ D + p_\ell \;\le\; \mathrm{OPT} + p_\ell \;\le\; \mathrm{OPT} + \mathrm{OPT} \;=\; 2\,\mathrm{OPT}, $$
> using the biggest-job bound $p_\ell \le \max_j p_j \le \mathrm{OPT}$. Since the
> busiest machine sets the makespan, greedy's makespan is at most $2\,\mathrm{OPT}$.
> $\qed$

The same two surrogates, sharpened, show that sorting jobs **longest-first** before
list-scheduling improves the ratio to $\tfrac43$ — a reminder that the order in
which a greedy commits often matters more than the greedy rule itself.[^graham-lpt]

::impl{algo="list_scheduling"}

## A knapsack FPTAS: approximation you can dial in

The algorithms so far hit a _fixed_ ratio. For some problems, any
accuracy $\varepsilon > 0$ is achievable: a
$(1+\varepsilon)$- (or $(1-\varepsilon)$-) approximation, paying in running time.
The **0/1 knapsack** problem is the textbook case, and its scheme is _fully_
polynomial — polynomial in both the input size _and_ $1/\varepsilon$.[^clrs-fptas]

Recall [knapsack](/algorithms/dynamic-programming/knapsack): items $1, \dots, n$
with weights $w_i$ and profits $p_i$, a capacity $W$; choose a subset of weight at
most $W$ maximizing total profit. There is an exact dynamic program indexed **by
profit** running in time $O(n^2 P)$, where $P = \max_i p_i$. That is fast when
profits are small but blows up when they are large — it is _pseudo_-polynomial,
polynomial in the value $P$, not in its bit-length.

The FPTAS exploits this dependence. Large profits are what inflate the
profit-indexed table, so we **scale them down and round**, shrinking the table
to a controllable size while distorting the answer only slightly.

```algorithm
caption: $\textsc{Knapsack-FPTAS}(w, p, W, \varepsilon)$ — $(1-\varepsilon)$-optimal profit
number: 4
$P \gets \max_i p_i$ // largest single profit
$\mu \gets \dfrac{\varepsilon P}{n}$ // scaling unit
for $i \gets 1$ to $n$ do
  $\hat p_i \gets \big\lfloor p_i / \mu \big\rfloor$ // round profits down
solve knapsack exactly on profits $\hat p$ by the profit-indexed DP
return that chosen subset (valued by the true $p_i$)
```

Rounding the profits to multiples of $\mu$ caps the scaled profits at
$\hat P = \lfloor P/\mu \rfloor = \lfloor n/\varepsilon \rfloor$, so the
profit-indexed DP now runs in time $O(n^2 \hat P) = O(n^3 / \varepsilon)$ —
polynomial in $n$ and in $1/\varepsilon$. It remains to bound the lost profit.

> **Theorem (Knapsack FPTAS).** For any $\varepsilon \in (0,1)$,
> $\textsc{Knapsack-FPTAS}$ returns a feasible solution of profit at least
> $(1-\varepsilon)\,\mathrm{OPT}$ in time $O(n^3 / \varepsilon)$.

> **Proof.** The DP is _exact_ on the rounded profits $\hat p$, so the subset $A$ it
> returns is at least as good, under $\hat p$, as the truly optimal subset $O$:
> $$ \sum_{i \in A} \hat p_i \;\ge\; \sum_{i \in O} \hat p_i. \qquad (\ast) $$
> Multiplying the floor inequality $\mu\,\hat p_i \le p_i \le \mu\,(\hat p_i + 1)$
> through, two bounds follow. First, $p_i \le \mu\,\hat p_i + \mu$, and second,
> $\mu\,\hat p_i \le p_i$. Now evaluate $A$'s true profit:
> $$
>   \sum_{i \in A} p_i \;\ge\; \mu \sum_{i \in A} \hat p_i
>     \;\overset{(\ast)}{\ge}\; \mu \sum_{i \in O} \hat p_i
>     \;\ge\; \sum_{i \in O} \parens{ p_i - \mu }
>     \;=\; \mathrm{OPT} - |O|\,\mu \;\ge\; \mathrm{OPT} - n\mu,
> $$
> using $|O| \le n$. Substitute $\mu = \varepsilon P / n$ to get $n\mu = \varepsilon P$,
> so
> $$ \sum_{i \in A} p_i \;\ge\; \mathrm{OPT} - \varepsilon P. $$
> Finally $P \le \mathrm{OPT}$, because any single item fits on its own (discard
> items heavier than $W$ up front), so the most valuable item is itself a feasible
> solution. Therefore
> $$ \sum_{i \in A} p_i \;\ge\; \mathrm{OPT} - \varepsilon\,\mathrm{OPT} \;=\; (1-\varepsilon)\,\mathrm{OPT}. \qquad\square $$

The two error sources are now visible. Rounding _down_ loses at most $\mu$ per
chosen item, hence at most $n\mu$ in total; the scaling choice $\mu = \varepsilon P/n$
makes that total exactly $\varepsilon P \le \varepsilon\,\mathrm{OPT}$. Smaller
$\varepsilon$ means finer $\mu$, a larger table, and a slower-but-sharper answer —
the running time grows as $1/\varepsilon$, never as an exponential.

::impl{algo="knapsack_fptas"}

## The hierarchy, and where approximation runs out

Naming the qualitative differences we have seen organizes the whole subject.

> **Definition (PTAS and FPTAS).**
>
> - A **polynomial-time approximation scheme (PTAS)** is a family of algorithms:
>   for each fixed $\varepsilon > 0$ one of them is a $(1+\varepsilon)$-approximation
>   running in time polynomial in $n$. The dependence on $\varepsilon$ may be awful
>   — even $n^{1/\varepsilon}$ is allowed.
> - A **fully polynomial-time approximation scheme (FPTAS)** is a PTAS whose running
>   time is also polynomial in $1/\varepsilon$ — like the knapsack scheme's
>   $O(n^3/\varepsilon)$.

An FPTAS is the strongest guarantee: accuracy becomes a parameter. The
guarantees form a hierarchy, each level strictly stronger than the one below.

$$
% caption: Approximability ladder, strongest to weakest. FPTAS (knapsack) gives any
%          ratio $1+\varepsilon$ in time poly in $n$ and $1/\varepsilon$; PTAS (Euclidean
%          TSP) is poly in $n$ only; constant ratio (vertex cover $2$, metric TSP $3/2$);
%          growing ratio (set cover, $\ln n$); inapproximable (general TSP) admits no
%          constant ratio unless $\mathsf{P}=\mathsf{NP}$.
\begin{tikzpicture}[font=\small,
    r/.style={draw, minimum width=72mm, minimum height=11mm,
              align=center, inner sep=3pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  \node[r, draw=green, fill=green!10] (fptas) at (0,3.6)
    {FPTAS: any ratio, time poly in size and in accuracy\\example: knapsack};
  \node[r, draw=acc, fill=acc!16] (ptas) at (0,2.0)
    {PTAS: any ratio, time poly in size only\\example: Euclidean TSP};
  \node[r, draw=acc, fill=acc!8] (const) at (0,0.4)
    {constant ratio: one constant factor\\examples: vertex cover, metric TSP};
  \node[r, draw=acc!60, fill=acc!4] (log) at (0,-1.2)
    {growing ratio: factor depends on size\\example: set cover};
  \node[r, draw=red!75!black, fill=red!8] (none) at (0,-2.8)
    {inapproximable: no constant factor\\example: general TSP};
  \draw[->, thick] (fptas) -- (ptas);
  \draw[->, thick] (ptas) -- (const);
  \draw[->, thick] (const) -- (log);
  \draw[->, thick] (log) -- (none);
  \node[anchor=west, font=\scriptsize, text=green] at (4.3,3.6) {strongest};
  \node[anchor=west, font=\scriptsize, text=red!75!black] at (4.3,-2.8) {weakest};
\end{tikzpicture}
$$

The bottom level is real: some problems admit no constant-factor approximation at
all, and the proofs are themselves reductions. The canonical example is the
**general** traveling-salesman problem, with no triangle inequality.[^erickson-inapprox]

> **Theorem (TSP inapproximability).** If $\mathsf{P} \neq \mathsf{NP}$, then for
> _no_ constant $\rho \ge 1$ is there a polynomial-time $\rho$-approximation for
> general TSP.

> **Proof (sketch).** Suppose a $\rho$-approximation $A$ existed. We use it to
> decide $\textsc{Hamiltonian-Cycle}$, an $\mathsf{NP}$-complete problem, in
> polynomial time. Given a graph $H$ on $n$ vertices, build a complete TSP instance
> on the same vertices: give each edge of $H$ cost $1$, and each non-edge the
> enormous cost $\rho \cdot n + 1$. If $H$ has a Hamiltonian cycle, the optimal tour
> uses only cost-$1$ edges and has length exactly $n$; then $A$ must return a tour
> of length at most $\rho n$, which is too small to include any expensive edge — so
> $A$'s tour is a Hamiltonian cycle of $H$. If $H$ has _no_ Hamiltonian cycle, every
> tour must use at least one expensive edge, so even $A$'s tour exceeds $\rho n$.
> The two cases are separated by the threshold $\rho n$, so reading off $A$'s tour
> length decides Hamiltonicity in polynomial time — impossible unless
> $\mathsf{P} = \mathsf{NP}$. $\qed$

The gap-creating trick — pricing non-edges so high that any decent approximation is
forced to avoid them — is the prototype for hardness-of-approximation. Its modern
descendant, the **PCP theorem**, constructs such gaps for a vast range of
problems, settling the _exact_ approximation threshold of MAX-3SAT, set cover,
and many others, and explaining why the ratios proved above so often turn out to be
the best possible.

::impl{algo="tsp_gap_reduction"}

## Tight thresholds and the approximability frontier

The gap reduction above shows _some_ ratio is unachievable; the modern
result is that the guarantees this lesson proved are often **exactly** optimal — the
algorithm and the hardness bound meet at the same constant. Three landmark results
draw that frontier:

- **Set cover is $\Theta(\ln n)$, tight.** The greedy $H_k \le 1 + \ln n$ ratio from
  earlier in this lesson cannot be improved: Feige (1998) proved that a
  $(1-\varepsilon)\ln n$-approximation for set cover would imply
  $\mathsf{NP} \subseteq \mathsf{DTIME}(n^{O(\log\log n)})$, essentially
  $\mathsf{P} = \mathsf{NP}$.[^feige] No polynomial algorithm for set cover can do
  better than greedy.
- **MAX-3SAT is $7/8$, tight.** A trivial random assignment satisfies $7/8$ of the
  clauses of a MAX-3SAT instance in expectation. Håstad (2001) proved via the PCP
  machinery that beating $7/8 + \varepsilon$ is $\mathsf{NP}$-hard — so the simplest
  possible algorithm is already optimal.[^hastad]
- **Dinur's combinatorial PCP.** The original PCP theorem's proof was famously
  intricate; Dinur (2007) gave a different **gap-amplification** proof
  that builds the required hardness gap incrementally, making inapproximability
  accessible without the heavy algebra.[^dinur]

$$
% caption: Algorithm and hardness meet: for set cover and MAX-3SAT the proved
%          approximation ratio equals the proved inapproximability threshold.
\begin{tikzpicture}[>=Stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9E55}
  % set cover row
  \node[anchor=east] at (-0.1,1.0) {set cover};
  \draw[green, very thick, ->] (0.4,1.0) -- (3.2,1.0);
  \node[green, anchor=west, font=\scriptsize] at (0.5,1.38) {greedy achieves it};
  \draw[red!75!black, very thick, ->] (7.2,1.0) -- (4.3,1.0);
  \node[red!75!black, anchor=east, font=\scriptsize] at (7.1,1.38) {Feige: no better};
  \node[acc] at (3.75,1.0) {$\ln n$};
  % max-3sat row
  \node[anchor=east] at (-0.1,-0.5) {MAX-3SAT};
  \draw[green, very thick, ->] (0.4,-0.5) -- (3.2,-0.5);
  \node[green, anchor=west, font=\scriptsize] at (0.5,-0.12) {random achieves it};
  \draw[red!75!black, very thick, ->] (7.2,-0.5) -- (4.3,-0.5);
  \node[red!75!black, anchor=east, font=\scriptsize] at (7.1,-0.12) {Hastad: no better};
  \node[acc] at (3.75,-0.5) {$0.875$};
\end{tikzpicture}
$$

One frontier remains genuinely open. The **Unique Games Conjecture** (Khot, 2002)
posits the hardness of a specific constraint problem; _if true_, it would fix
the exact approximation threshold of a wide range of problems at once,
including vertex cover (making our factor-$2$ optimal) and MAX-CUT.[^ugc] Whether
UGC holds is one of the central open questions of complexity theory today.

## Takeaways

- An **approximation algorithm** runs in polynomial time with a provable bound on
  how far from optimal it can land. The **relative ratio** $\rho$ (cost
  $\le \rho\,\mathrm{OPT}$ for minimization, $\ge \mathrm{OPT}/\rho$ for
  maximization) is the standard guarantee; **absolute** additive guarantees are
  rare because hard problems scale.
- Every proof bounds the output against a **surrogate** for the unknown optimum: a
  charging argument for **greedy set cover** ($H_n \approx \ln n$, and no
  polynomial algorithm beats $\ln n$), the **MST** for metric TSP
  ($c(T) \le \mathrm{OPT}$ gives a $2$-approximation; Christofides sharpens it to
  $\tfrac32$), and two universal lower bounds (average load, biggest job) for
  **list-scheduling** makespan ($2$-approximation).
- A **PTAS** achieves any ratio $1+\varepsilon$ in time polynomial in $n$; an
  **FPTAS** is also polynomial in $1/\varepsilon$. The **knapsack FPTAS** scales and
  rounds profits to shrink the pseudo-polynomial DP, losing at most $n\mu = \varepsilon P
  \le \varepsilon\,\mathrm{OPT}$.
- Some problems are **inapproximable**: unless $\mathsf{P} = \mathsf{NP}$, **general
  TSP** has no constant-factor approximation, shown by pricing non-edges to create a
  gap that would otherwise decide Hamiltonicity. Hardness of approximation is
  proved by reductions, just like $\mathsf{NP}$-hardness itself.

[^clrs-setcover]: **CLRS**, Ch. 35 — Approximation Algorithms (§35.3): the greedy set-cover heuristic and its $H_n = O(\ln n)$ approximation bound via the per-element charging argument.
[^lund-yannakakis]: **CLRS**, Ch. 35 — Approximation Algorithms: greedy set cover is essentially optimal; under $\mathsf{P} \neq \mathsf{NP}$ no polynomial algorithm achieves ratio $(1-o(1))\ln n$.
[^clrs-tsp]: **CLRS**, Ch. 35 — Approximation Algorithms (§35.2): the MST-doubling $2$-approximation for metric (triangle-inequality) TSP, with $c(T) \le \mathrm{OPT}$ and shortcutting bounded by the triangle inequality.
[^christofides]: **Skiena**, §11.10 — Approximation Algorithms: Christofides' $\tfrac32$-approximation for metric TSP, fixing odd-degree parity with a minimum-weight perfect matching instead of doubling the whole tree.
[^graham-lpt]: **CLRS**, Ch. 35 — Approximation Algorithms (Problem 35-5): list scheduling for makespan is a $2$-approximation; the longest-processing-time rule improves the bound to $\tfrac43$.
[^clrs-fptas]: **CLRS**, Ch. 35 — Approximation Algorithms (§35.5): the fully polynomial-time approximation scheme for the subset-sum / knapsack problem by trimming and scaling, giving $(1-\varepsilon)\,\mathrm{OPT}$ in time polynomial in $n$ and $1/\varepsilon$.
[^erickson-inapprox]: **Erickson**, Ch. 12 — NP-Hardness: gap reductions and inapproximability, including the proof that general TSP admits no constant-factor approximation unless $\mathsf{P} = \mathsf{NP}$.
[^feige]: Uriel Feige, "A Threshold of $\ln n$ for Approximating Set Cover," _Journal of the ACM_ 45(4), 1998 — the matching hardness lower bound making greedy optimal for set cover.
[^hastad]: Johan Håstad, "Some Optimal Inapproximability Results," _Journal of the ACM_ 48(4), 2001 — the tight $7/8$ threshold for MAX-3SAT and other optimal PCP-based inapproximability results.
[^dinur]: Irit Dinur, "The PCP Theorem by Gap Amplification," _Journal of the ACM_ 54(3), 2007 — a combinatorial gap-amplification proof of the PCP theorem.
[^ugc]: Subhash Khot, "On the Power of Unique 2-Prover 1-Round Games," _STOC_ 2002 — the Unique Games Conjecture, which if true fixes the optimal approximation ratio for vertex cover, MAX-CUT, and many others.