Approximation Algorithms

Many of the most useful problems in computing are NP-hard: as the input grows, every known method for finding the exact best answer blows up to astronomical running times. Routing fleets, placing cell towers, scheduling factories — the optimal solution is in there somewhere, but we cannot afford to wait centuries to find it.

So we change the question. Instead of "give me the perfect answer," we ask "give me an answer that is good, fast, and — crucially — that comes with a promise."

An approximation algorithm is a fast algorithm that returns a solution together with a proven guarantee about how far it can be from optimal. A "2-approximation", for example, never returns a result more than twice as costly as the very best possible — and it does so in a blink. You give up the last sliver of quality and, in exchange, you get speed plus a guarantee you can take to the bank.

Vertex cover asks: pick the fewest vertices so that every edge touches at least one chosen vertex. Finding the smallest such set is NP-hard. But there is a beautifully simple 2-approximation: while any edge is still uncovered, grab both of its endpoints. The result is never more than twice the optimum.

<p class="hint">{{hint}}</p>
<svg id="graph" viewBox="0 0 320 220" class="graph"></svg>
<div class="scores">
  <span class="score" id="approxScore">{{lbl_approx}} &mdash;</span>
  <span class="score" id="optScore">{{lbl_opt}} &mdash;</span>
  <span class="score" id="ratio">{{lbl_ratio}} &mdash;</span>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="approx" type="button">{{btn_approx}}</button>
  <button id="opt" type="button">{{btn_opt}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.graph { width: 100%; max-width: 360px; height: auto; display: block; margin: 0 auto .4rem; }
.edge { stroke: #adb1b8; stroke-width: 3; }
.edge.covered { stroke: #0a7d33; }
.edge.active { stroke: #e63946; stroke-width: 4; }
.node { fill: #c9ccd1; stroke: #8a8f97; stroke-width: 2; }
.node.approx { fill: #1d3557; stroke: #14253f; }
.node.opt { fill: #e9b949; stroke: #b9902a; }
.nlabel { font: 700 12px ui-monospace, monospace; fill: #1d3557; pointer-events: none; }
.scores { display: flex; gap: .6rem; flex-wrap: wrap; margin: .3rem 0; }
.score { font: 600 13px ui-monospace, monospace; background: #eef2f6; border: 1px solid #d4dde6;
         padding: .25rem .55rem; border-radius: 6px; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Press Run 2-approximation to watch the greedy rule pick endpoints edge by edge, then Find true optimum to brute-force the smallest possible cover. Compare the two numbers: here greedy uses 4 vertices and the true minimum is 3, a ratio of about 1.33× — well inside the promised 2×, and computed instantly. The ratio you see is the guarantee made visible.

Finding an exact minimum vertex cover is NP-hard — equivalent to the whole P vs NP family, so no fast exact algorithm is known. Yet approximation reshapes the picture entirely:

• The 2-approximation is provable. The greedy rule picks the endpoints of a maximal matching. Every edge in that matching needs at least one endpoint in any cover, so the optimum is at least the matching size; we took both endpoints, exactly twice as many. Result: ALG ≤ 2 · OPT, guaranteed, in linear time.
• Quality has a price tag. The number out front — 2 here — is the approximation ratio. Lower is better; a ratio of 1 would mean exact.
• Some problems approximate to perfection. Knapsack and many scheduling problems admit a PTAS: dial the ratio as close to 1 as you like (1.1×, 1.01×, ...) at the cost of more time.
• Others are provably resistant. The PCP theorem (Arora, Lund, Motwani, Sudan, Szegedy, 1992) shows that for problems like Max-Clique, even approximating the answer is NP-hard. Vertex cover itself cannot be approximated below 1.36× unless P = NP, and under the Unique Games Conjecture not below 2× — so our humble greedy rule may already be essentially the best possible.

Approximation does not dodge NP-hardness; it negotiates with it, and the terms differ wildly from problem to problem.

Almost every large optimization that ships in production is, under the hood, an approximation with a guarantee:

• Logistics and routing: delivery and ride-hailing systems lean on approximations of the traveling-salesman tour rather than the unreachable exact optimum.
• Network and facility design: placing servers, warehouses or cell towers maps onto set cover and facility location, classic approximation targets.
• Scheduling: assigning jobs to machines to finish as early as possible uses simple greedy rules with proven worst-case bounds.
• Clustering and data: k-center and k-means style placements use constant-factor approximations because exact optima are NP-hard.

The shared lesson: when you cannot afford the perfect answer, a provable near-perfect answer — delivered fast — is usually what the real world needs. Vertex cover is the friendly doorway; set cover and routing are where it pays off.

Approximation algorithms are computer science making peace with the hardest problems it knows. We accept that the perfect answer is out of reach, and in return we demand something the perfect answer rarely offers: speed plus a mathematical promise about how close we are.

The 2-approximation for vertex cover captures the whole idea in one line of greed: grab both ends of an uncovered edge, repeat, and you are guaranteed to finish within twice the best possible. That is the quiet triumph behind so much working software — not solving P vs NP, but getting provably, usefully close to its hardest corners.