Symptom

You have accepted that the problem is NP-hard. Now what?

The literature offers a wall of results with numbers attached: 2-approximation, $\ln n$-approximation, PTAS, FPTAS, 0.878. Nobody explains what these numbers buy you, how they are proved, or how they connect to the heuristic you already wrote. Meanwhile your greedy heuristic is running in production and you have no idea whether it is within 5% or a factor of 50 of optimal, because you cannot compute the optimum to compare against — that was the whole problem.

That last point is the one that stings. Measuring approximation quality seems to require solving the problem you cannot solve.

It does not, and the technique for getting around it is the actual content of this subject.

Statement

An algorithm is an $\alpha$-approximation for a minimization problem if it runs in polynomial time and always returns a solution of cost at most $\alpha \cdot \text{OPT}$. For maximization, at least $\alpha \cdot \text{OPT}$ with $\alpha \le 1$. The guarantee holds on every input, which is what separates this from a heuristic.

The landscape, in increasing order of good news:

  • No constant factor. Set cover: $\Theta(\ln n)$, and by T031 that is optimal. General TSP: no constant-factor approximation at all unless P = NP.
  • Constant factor (APX). Vertex cover at 2, metric TSP at 3/2, max-cut at 0.878. These do not admit a PTAS unless P = NP.
  • PTAS. For any $\epsilon > 0$, a $(1+\epsilon)$-approximation in time polynomial in $n$ — but possibly $n^{1/\epsilon}$, which is polynomial and useless. Euclidean TSP has one.
  • FPTAS. Time polynomial in both $n$ and $1/\epsilon$. Knapsack has one. This is the best possible category, and strongly NP-hard problems cannot have one.

The key structural fact: exact-solution equivalence does not survive. All of Karp’s 21 are equally hard exactly, and they scatter across every one of these classes. “NP-hard” tells you almost nothing about how well you can approximate.

Argument

Vertex cover, 2-approximation, and the bounding trick. Find any maximal matching $M$ — repeatedly grab an uncovered edge and delete both endpoints — and output all $2|M|$ endpoints.

Feasible: if some edge were uncovered, both endpoints would be free and the matching was not maximal.

Within 2: the edges of $M$ are disjoint, so any cover must contain at least one endpoint of each, giving $\text{OPT} \ge |M|$. We output $2|M| \le 2,\text{OPT}$.

That is the whole technique, and it answers the symptom. We never computed OPT. We found a quantity — the matching size — that is provably a lower bound on OPT and provably close to our output. Every approximation guarantee is built this way: bound OPT from the side you can compute. Once you internalize this, you can go and bound your own production heuristic.

Greedy set cover, $\ln n$. Repeatedly take the set covering the most uncovered elements. If $k$ sets suffice, some set covers at least a $1/k$ fraction of what remains, so each greedy step leaves at most a $(1 - 1/k)$ fraction. After $k \ln n$ steps, at most $n(1-1/k)^{k\ln n} \le n e^{-\ln n} = 1$ element remains. So greedy uses at most $k \ln n$ sets, a ratio of $\ln n$ — about 13.8 at a million elements. By T031 no polynomial algorithm does better, so greedy is not merely good, it is final.

Knapsack’s FPTAS, by rounding. The exact dynamic program runs in $O(n V)$ where $V$ is total value — pseudo-polynomial, exponential in bit length. Scale every value down by $\epsilon v_{\max}/n$ and round. Each item loses at most $\epsilon v_{\max}/n$, so $n$ items lose at most $\epsilon v_{\max} \le \epsilon ,\text{OPT}$. The scaled DP runs in $O(n^3/\epsilon)$. Throwing away low-order bits of the input is the whole trick, and it is polynomial in $1/\epsilon$, so $\epsilon = 0.01$ is genuinely runnable.

LP relaxation and rounding, the general-purpose method. Write the problem as an integer program, drop the integrality constraint, and solve the LP in polynomial time. The LP optimum bounds the integer optimum — again, a computable bound on OPT. Then round the fractional solution to an integer one. For vertex cover, rounding every $x_v \ge 1/2$ up gives 2-approximation again, and the LP has a half-integral optimum which makes the analysis clean.

The integrality gap is the method’s ceiling. The worst-case ratio between the integer and LP optima bounds what any LP-rounding argument can achieve. Set cover’s LP gap is $\Theta(\log n)$, so no amount of clever rounding beats greedy. Knowing the gap tells you when to stop trying, which is the same service T031 provides one level up.

Randomized rounding, and derandomization. Treat fractional $x_i$ as a probability, include $i$ with that probability, and use linearity of expectation (T007) plus a concentration bound (T008). MAX-SAT’s 3/4-approximation combines randomized rounding with a naive random assignment and takes the better of the two. Goemans–Williamson’s 0.878 for max-cut solves a semidefinite relaxation and rounds by a random hyperplane, which is where the odd constant comes from — it is $\min_\theta \frac{2\theta}{\pi(1-\cos\theta)}$, not a design choice.

Primal-dual and local search round out the toolkit: build a feasible dual solution alongside the primal to certify the bound, or make local improvements until stuck and argue the local optimum is globally close. Both are in Williamson and Shmoys, and both give combinatorial algorithms with no LP solver in the loop.

Tightness, and why 2 is really 2. The vertex cover analysis is not loose. A complete bipartite graph $K_{n,n}$ has a maximal matching of size $n$, so the algorithm returns all $2n$ vertices, while the optimum is one side, $n$ vertices. The ratio is exactly 2 on an infinite family, so no sharper analysis of this algorithm exists. Approximation ratios come in pairs — an upper bound from the analysis and a matching lower bound from an adversarial family — and a result without both halves has not been finished.

The same discipline explains why greedy set cover is stated as $\ln n$ rather than something better: there is a known family of instances on which greedy really does use $\ln n$ times the optimal number of sets.

Forbids

A PTAS for APX-hard problems, unless P = NP. Vertex cover, max-cut and metric TSP have hard constant floors, so pushing a 2-approximation to 1.01 is not an engineering project.

An FPTAS for strongly NP-hard problems. TSP, graph colouring, bin packing in the general sense. The FPTAS route depends on a pseudo-polynomial algorithm, and strong NP-hardness rules that out.

Constant-factor approximation of general TSP. Without the triangle inequality, a constant-factor approximation would solve Hamiltonian circuit. Metric structure is doing essential work, not simplifying the analysis.

Guarantees from unanalyzed heuristics. A heuristic without a bounding argument has no worst case you can state. That is often fine, and it is not the same thing.

Does not forbid

It does not mean approximation ratios predict practical quality. LKH — a local-search TSP heuristic with no constant-factor guarantee at all — routinely lands within 1% of optimal on instances where Christofides’s guaranteed 3/2 is far worse in practice. The guaranteed algorithm often loses to the unguaranteed one on real inputs, and this is the most important thing to know before choosing based on the published ratio.

It does not mean the worst case is your case. First-fit-decreasing bin packing has a worst-case ratio of 11/9, and averages around 2% above optimal on realistic item distributions. Ratios are adversarial.

It does not mean exact solvers are out of the question. Concorde solves TSP instances with tens of thousands of cities to proven optimality; Gurobi and CPLEX solve enormous integer programs exactly with branch-and-cut. If you need the optimum and can wait, exact is frequently available, and reaching for an approximation reflexively is a mistake.

It does not mean a PTAS is usable. A $(1+\epsilon)$ algorithm running in $n^{O(1/\epsilon^2)}$ is polynomial and unrunnable at $\epsilon = 0.1$. The early Euclidean TSP PTASes had exactly this character. “Has a PTAS” is a classification fact, not a recommendation.

It does not mean approximation and heuristics are rivals. The standard production pattern is a guaranteed algorithm for a starting solution plus local search to improve it, keeping the bound while capturing practical gains. You do not have to choose.

Boundary

  • Bicriteria approximation. Relax feasibility as well as objective: a $(2,3)$-approximation might give twice the cost with three times the resource cap. Frequently the right trade in scheduling and clustering when a hard constraint is soft in reality.
  • Resource augmentation. Compare your algorithm on $m$ machines against the optimum on fewer, which is how competitive-analysis pessimism gets tamed and the standard framing for online scheduling.
  • Online approximation is a different beast. Competitive ratios bound performance without knowledge of the future. Graham’s list scheduling is $(2 - 1/m)$-competitive — 1.875 on eight machines — with no future knowledge at all, which is a strong result for an online algorithm.
  • Where the ratio comes from is a design decision. Combinatorial arguments give simple fast algorithms with weaker bounds; LP and SDP rounding give stronger bounds at the cost of solving a relaxation per instance. In production the combinatorial version usually wins on operability.
  • Parameterized approximation combines this post with T033: allow $f(k)\cdot n^{O(1)}$ time and a $(1+\epsilon)$ factor, and some problems hard under either relaxation alone become tractable under both.