Approximation Algorithms

When exact optimisation is NP-hard, settle for a provable ratio.

An algorithm is a $\rho$-approximation if, for every input,

$\frac{\mathrm{ALG}}{\mathrm{OPT}}\le \rho \text{ (minimisation)}\text{or}\frac{\mathrm{ALG}}{\mathrm{OPT}}\ge \rho \text{ (maximisation)}.$

The ratio landscape

Problem	Best ratio	Hardness
Vertex cover	2	no better than 1.36 (2 under UGC)
Metric TSP	$\frac{3}{2}$ (Christofides)	no PTAS
Euclidean TSP	$1+\epsilon$ (PTAS)	—
General TSP	none	no constant factor unless P=NP
Set cover	$\ln n$	$(1-\epsilon )\ln n$ is hard
Max cut	0.878 (Goemans-Williamson)	optimal under UGC
Max SAT	0.797
Knapsack	FPTAS ($1+\epsilon$)	—
Bin packing	$\frac{11}{9}\mathrm{OPT}+\frac{6}{9}$ (FFD)	asymptotic PTAS exists
Makespan	$\frac{4}{3}$ (LPT); PTAS	—
Max independent set	$n^{1-\epsilon }$	essentially inapproximable
Steiner tree	$\ln 4+\epsilon \approx 1.386$
Facility location	1.488

Two lessons: the achievable ratio varies enormously between superficially similar problems, and many of the best ratios are provably optimal (assuming P≠NP or the Unique Games Conjecture).

The main techniques

1. Greedy with a bound

Set cover: repeatedly take the set covering the most uncovered elements → $H_n\approx \ln n$ approximation. The analysis charges each element the cost at the moment it was covered.

Vertex cover: take both endpoints of any uncovered edge → 2-approximation, since any cover must include at least one endpoint of each matched edge.

2. LP relaxation and rounding

Relax the integrality constraint, solve the LP, and round. The LP value bounds OPT, which gives the ratio. See randomized rounding.

Vertex cover: solve the LP; the optimum is half-integral, so rounding every $x_v\ge \frac{1}{2}$ up gives a 2-approximation directly.

3. SDP relaxation

Goemans-Williamson for MAX-CUT: relax to unit vectors, solve the SDP, and cut with a random hyperplane → 0.878.

4. Primal-dual

Build a feasible solution and a dual certificate simultaneously; the ratio falls out of weak duality. Used for facility location and Steiner forest.

5. Local search

Start anywhere; improve while possible. The ratio follows from the local-optimality conditions. Simple, and often surprisingly good ($k$-median, max cut).

6. Dynamic programming + rounding (FPTAS)

Round the values so the DP table becomes small enough. Knapsack: divide values by $\frac{\epsilon v_{\max }}{n}$ and run the value-indexed DP → $(1-\epsilon )$ in $O(n^3/\epsilon )$.

PTAS and FPTAS

Class	Running time	Example
PTAS	polynomial in $n$ for each fixed $\epsilon$ (may be $n^{1/\epsilon }$)	Euclidean TSP, makespan
FPTAS	polynomial in $n$ and $1/\epsilon$	knapsack, subset sum
APX	constant-factor approximable	vertex cover, metric TSP
No constant factor		general TSP, max clique

A strongly NP-hard problem has no FPTAS unless P=NP. Knapsack has one precisely because it is only weakly NP-hard (its pseudo-polynomial DP is what gets rounded).

The knapsack FPTAS

// (1-eps)-approximation for 0/1 knapsack
double K = eps * maxValue / n;
for (auto& item : items) item.v = (long long)(item.v / K);      // scale down
// now run the value-indexed DP: dp[v] = minimum weight to achieve value v
// total value range is O(n / eps), so the DP is O(n^2 / eps)

The rounding loses at most $\epsilon v_{\max }\le \epsilon \mathrm{OPT}$ in total.

In competitive programming

Approximation ratios rarely appear directly — problems want exact answers. Where the ideas do help:

Use	How
Marathon / optimisation contests	ratios justify a construction; see heuristics
Bounding a greedy’s quality	to decide whether it can be optimal
Recognising NP-hardness	if the problem is a known APX-hard one, stop looking for an exact polynomial algorithm
Branch and bound	approximation gives a good incumbent and a pruning bound
Constructive problems	”any solution within $k$ of optimal” is sometimes the actual requirement

The most practical takeaway is negative: if you recognise the problem as NP-hard, stop searching for a polynomial exact algorithm and look at the constraints again — they will point to bitmask DP, meet in the middle, or a heuristic.

See also: Greedy Approximations · Christofides · Exact / NP-Hard