Approximation Algorithms — Trading Exactness for a Guarantee

The craft of giving up on the optimal answer while attaching a price tag that reads "never worse than X times optimal". We build up the approximation ratio, carry a greedy proof all the way to the end, and see why the triangle inequality flips the entire conclusion for the traveling salesman problem.

The metaphor: the perfect delivery route arrives after dark

One truck, thirty stops, and you want the shortest possible order to visit them. The number of routes is $29!/2 \approx 4.4 \times 10^{30}$. You can write the brute-force loop in ten lines, but the company will be gone before it prints an answer.

Meanwhile the veteran dispatcher glances at the map and says "roughly this order" in ten seconds. Fast. The catch is that nobody — including the dispatcher — knows whether that route is 20% worse than the best one or three times worse.

Approximation algorithms stand between those two. They finish in polynomial time, and the answer they hand back comes with a price tag: never worse than some fixed multiple of the optimum. You give up exactness, and in exchange you get a mathematical bound on exactly how much you gave up. That is the deal this field offers.

Why the deal is necessary is the subject of NP-Completeness from Scratch: the traveling salesman, scheduling, and bin packing problems have no realistic prospect of an exact polynomial-time solution. Once you know a problem is hard, this is the most disciplined thing you can do next.

The approximation ratio — putting a number on "close enough"

Nothing works until "close" is defined. Take a minimization problem, where you want to shrink a distance or a cost. Write $\mathrm{ALG}(I)$ for the cost of the solution your algorithm returns on input $I$, and $\mathrm{OPT}(I)$ for the cost of the optimal solution.

In words, equation (1) says: whatever input someone throws at you, the cost of your answer never exceeds $\rho$ times the optimum. The $\max_I$ is an adversary picking the worst possible input, and a $\rho$ that survives even that is called the approximation ratio. An algorithm with $\rho = 2$ is a "2-approximation". The ratio is always at least 1, and closer to 1 is better.

For maximization problems — profit, coverage, anything you want to grow — the inequality flips and we write $\mathrm{ALG} \ge \mathrm{OPT}/\rho$. Either direction runs straight into the same wall:

You are approximating precisely because you cannot compute the optimum. So how can you possibly guarantee a ratio against it?

How the guarantee is built — comparing to an optimum you never compute

The trick is to never touch $\mathrm{OPT}$ directly, and instead route the argument through a quantity you know sits below it. That quantity is called a lower bound.

In plain English, equation (2) reads: your answer is within $c$ times some quantity $\mathrm{LB}$ that you can actually get your hands on, and that $\mathrm{LB}$ is no larger than the optimum, therefore your answer is within $c$ times the optimum. The point is that $\mathrm{LB}$ sits in the middle where you can work with it. The left inequality follows from tracing what your algorithm does; the right one follows from the structure of the problem. You end up bounding your distance from the optimal solution without ever identifying what that solution is.

Most papers in this field spend far more effort finding a good lower bound than inventing the greedy rule itself. Every proof below has this shape, so equation (2) is the only thing you need to hold in your head.

Before going further, it helps to feel why exactness gets abandoned at all.

One greedy proof, carried to the end — vertex cover

Vertex cover asks for the smallest set of vertices such that every edge in a graph has at least one of its two endpoints in the set. Think of placing cameras at intersections so that every street is watched. It is NP-hard, and the obvious idea — repeatedly grab the vertex of highest degree — turns out to admit inputs where it lands a factor of $\log n$ off. Instead, an almost insultingly simple procedure gets you a 2-approximation.

1. Pick any edge $(u,v)$ that is not yet covered
2. Put both endpoints $u$ and $v$ into the solution
3. Delete every edge touching $u$ or $v$, and repeat until no edges remain

Here is why it is a 2-approximation, poured into the mold of equation (2). Call the set of edges picked in step 1 $M$. No two edges in $M$ share an endpoint, because the moment an edge is picked, everything touching its endpoints is deleted. A set of edges with no shared endpoints is called a matching.

• Upper bound: the output $C$ takes two vertices per edge of $M$, so $|C| = 2|M|$.
• Lower bound: any vertex cover must contain at least one endpoint of each edge in $M$ in order to cover it. Since the edges of $M$ share no endpoints, that "at least one" is a different vertex for each edge. Hence $\mathrm{OPT} \ge |M|$.

Put them together: $|C| = 2|M| \le 2\,\mathrm{OPT}$. Slotting $\mathrm{LB} = |M|$ into the middle is the entire proof.

def vertex_cover_2approx(edges):          # edges: [(u, v), ...]
    cover = set()
    for u, v in edges:
        if u not in cover and v not in cover:   # an edge not yet covered
            cover.add(u)                        # take BOTH endpoints
            cover.add(v)
    return cover

Taking both endpoints looks wasteful, and that waste is exactly where the guarantee comes from. "Improve" it to take only the higher-degree endpoint and the lower-bound argument collapses; you can no longer claim a factor of 2. Modify the procedure and you must redo the proof — a principle that keeps mattering below.

For what it is worth, 2 is close to the end of the road. Beating a factor of 1.3606 is NP-hard (Dinur–Safra, 2005), and under the Unique Games Conjecture even $2-\varepsilon$ is out of reach. Half a century on, nobody has meaningfully beaten the procedure on page one of the textbook.

When greedy drifts to a log factor — set cover

Set cover asks you to pick the fewest sets from a collection so that every element is covered. It shows up as staffing a team that covers every required skill, or picking the smallest suite of regression tests that touches every feature.

The greedy rule here is just as natural: repeatedly take the set that covers the most still-uncovered elements. Ten lines of code. But the ratio is not a constant — there are inputs that push it to $H_n = 1 + \tfrac12 + \dots + \tfrac1n \approx \ln n$. With a million elements that is roughly a factor of 14.