Approximation Algorithms

For NP-hard objectives, polynomial methods with proven fractions of optimal beat exact search that never finishes.

$Exact search explodes over subsets while greedy climbs steadily to a proven fraction of the optimum$

Exact search explodes over subsets while greedy climbs steadily to a proven fraction of the optimum

Why Does This Exist?

Exact data selection, clustering, and routing are NP-hard at ML scales, yet decisions must ship. Approximation algorithms run in polynomial time with proven ratios: the answer is always within a stated fraction of optimal (maximization) or factor above it (minimization). The ratio replaces hope with bookkeeping: a $0.63$ guarantee on a $900$ -concept coverage problem certifies $567$ regardless of instance. Hardness context is P versus NP; sublinear data access is sketching.

The one idea you need first

An $\alpha$ -approximation for maximization returns value at least $\alpha \times OPT$ with $0 < \alpha \le 1$ (for minimization, at most $\alpha \times OPT$ with $\alpha \ge 1$ ). Smaller $\alpha$ above one (minimization) or larger below one (maximization) is better; a PTAS approaches $1$ in polynomial time per fixed accuracy.

Think of It Like This

Packing a moving truck against the clock

The movers cannot try every loading order: the truck leaves in an hour. They place the bulkiest fitting box first, then the next, never unloading. The truck fills to a proven share of the best packable volume because each placement captures at least its fair fraction of the remaining gap.

Exact packing (try every order) is the exponential search; greedy loading is the approximation. The guarantee is the lease with the customer: whatever the optimal pack, this truck carries a certified fraction. Different cargo (fragile, nested) needs different rules, which is why ratios come with structural premises.

How It Actually Works

Greedy submodular maximization. For monotone submodular $f$ (diminishing returns) with cardinality $k$ , iteratively add the element with largest marginal gain. Guarantee: $1 - 1/e \approx 0.63$ of optimal (Nemhauser). LP rounding. Solve the linear relaxation, round fractionally: vertex cover via maximal matching gives factor $2$ ; metric TSP via MST doubling gives $1.5$ (Christofides). Schemes. Knapsack has an FPTAS: $(1 - \epsilon)$ -optimal in time polynomial in $n$ and $1/\epsilon$ .

Tightness: the greedy $0.63$ is best possible for submodular maximization with value queries alone (information-theoretic wall), so beating it needs more structure.

Worked example

Cover $900$ reachable concepts with $k = 10$ sensors, each sensor covering a known subset. Optimum $900$ . Greedy picks: $200, 150, 110, 80, 60, 40, 30, 20, 15, 12$ new concepts per step (diminishing, as submodularity predicts), totaling $717 \ge 567 = 0.63 \times 900$ . Certificate delivered with $10$ greedy steps against $\binom{n}{10}$ exact search. Vertex-cover twin: maximal matching of $6$ edges certifies a cover of $12$ vertices against optimum at least $6$ : factor $2$ in one line.

Code

1def greedy(values: list[list[float]], k: int) -> float:2    covered, total = set(), 0.03    pool = [set(v) for v in values]  # each sensor's concept set4    for _ in range(k):5        nxt = max(pool, key=lambda s: len(s - covered))  # best marginal gain6        total += len(nxt - covered)7        covered |= nxt8    return total9
10
11sensors = [{i} for i in range(10)] + [{0, 1, 2}]12print(greedy(sensors, 2))  # -> 2.0 (two fresh singletons beat the triple)

Marginal-gain picks total $2$ : the diminishing-returns rule choosing breadth over overlap.

Watch Out For

Quoting 0.63 for non-submodular scores

With repulsion or synergy between picks (diverse batches, interacting features), marginal gains need not diminish and greedy can score arbitrarily poorly. Test diminishing returns on your objective (pairwise swap checks) before certifying anything.

Rounding LPs without checking integrality gaps

A relaxation with a large integrality gap caps every rounding scheme: the fractional optimum itself is far above integer OPT, so no rounding recovers the ratio you hoped. Compute the gap on small instances first; reformulate (stronger cuts) when it yawns.

The Quick Version

Approximation certifies fractions of optimal in polynomial time on NP-hard tasks.
Greedy submodular maximization guarantees $1 - 1/e \approx 0.63$ ; the example reaches $717$ of $900$ .
Vertex cover rounds to factor $2$ ; metric TSP tours to $1.5$ ; knapsack admits an FPTAS.
The $0.63$ is information-theoretically tight for value-query methods.
Verify diminishing returns before quoting greedy ratios.
Check integrality gaps before designing rounding schemes.