Introduction

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.

Approximation vs Optimal

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">Vertex cover: choose the fewest dots so that <b>every</b> line touches a chosen dot. The greedy <b>2-approximation</b> repeatedly grabs <b>both</b> endpoints of an uncovered line. It is fast and provably never worse than 2&times; the true optimum.</p>
<svg id="graph" viewBox="0 0 320 220" class="graph"></svg>
<div class="scores">
  <span class="score" id="approxScore">2-approx: &mdash;</span>
  <span class="score" id="optScore">optimum: &mdash;</span>
  <span class="score" id="ratio">ratio: &mdash;</span>
</div>
<div class="status" id="status">Run the greedy rule, then find the true optimum.</div>
<div class="btns">
  <button id="approx" type="button">Run 2-approximation</button>
  <button id="opt" type="button">Find true optimum</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Vertex cover: choose the fewest vertices so every edge has at least one chosen endpoint.
// Exact minimum is NP-hard. Greedy 2-approximation: while an edge is uncovered, take BOTH
// endpoints (the endpoints of a maximal matching). Theorem: |greedy| <= 2 * |optimum|.
const NODES = [
  {id:0, x: 55, y: 45}, {id:1, x:160, y: 30}, {id:2, x:265, y: 45},
  {id:3, x: 50, y:175}, {id:4, x:160, y:110}, {id:5, x:265, y:180}
];
// A small graph with a hub (node 4). Order matters for the greedy walk:
// grabbing a hub edge first lets greedy cover cheaply, beating the worst case.
const EDGES = [[4,0],[4,1],[4,2],[4,3],[4,5],[0,1],[2,5]];

let approxSet = new Set();
let optSet = new Set();

function neighborsCovered(cover){ return EDGES.every(([a,b]) => cover.has(a) || cover.has(b)); }

// Greedy 2-approximation over the edge list.
function greedyCover(){
  const cover = new Set();
  const picks = [];
  for(const [a,b] of EDGES){
    if(!cover.has(a) && !cover.has(b)){ cover.add(a); cover.add(b); picks.push([a,b]); }
  }
  return {cover, picks};
}

// Brute force: smallest subset of vertices that covers every edge.
function optimumCover(){
  const n = NODES.length; let best = null;
  for(let mask=0; mask<(1<<n); mask++){
    const s = new Set();
    for(let i=0;i<n;i++) if(mask&(1<<i)) s.add(i);
    if(neighborsCovered(s) && (best===null || s.size<best.size)) best = s;
  }
  return best;
}

function render(){
  const svg = document.getElementById('graph'); svg.innerHTML='';
  const NS='http://www.w3.org/2000/svg';
  EDGES.forEach(([a,b])=>{
    const ln=document.createElementNS(NS,'line');
    const A=NODES[a],B=NODES[b];
    ln.setAttribute('x1',A.x);ln.setAttribute('y1',A.y);
    ln.setAttribute('x2',B.x);ln.setAttribute('y2',B.y);
    let cls='edge';
    if(approxSet.has(a)||approxSet.has(b)) cls+=' covered';
    ln.setAttribute('class',cls); svg.appendChild(ln);
  });
  NODES.forEach(nd=>{
    const c=document.createElementNS(NS,'circle');
    c.setAttribute('cx',nd.x);c.setAttribute('cy',nd.y);c.setAttribute('r',16);
    let cls='node';
    if(approxSet.has(nd.id)) cls+=' approx';
    else if(optSet.has(nd.id)) cls+=' opt';
    c.setAttribute('class',cls); svg.appendChild(c);
    const t=document.createElementNS(NS,'text');
    t.setAttribute('x',nd.x);t.setAttribute('y',nd.y+4);
    t.setAttribute('text-anchor','middle');t.setAttribute('class','nlabel');
    t.style.fill = (approxSet.has(nd.id)) ? '#fff' : '#1d3557';
    t.textContent=nd.id; svg.appendChild(t);
  });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function updateScores(){
  document.getElementById('approxScore').textContent = fmt('2-approx: %v%', { v: approxSet.size||'—' });
  document.getElementById('optScore').textContent = fmt('optimum: %v%', { v: optSet.size||'—' });
  if(approxSet.size && optSet.size){
    const r=(approxSet.size/optSet.size).toFixed(2);
    document.getElementById('ratio').textContent = fmt('ratio: %r%×', { r: r });
  } else document.getElementById('ratio').textContent = 'ratio: —';
}

function runApprox(){
  optSet=new Set();
  const {cover}=greedyCover(); approxSet=cover; render(); updateScores();
  setStatus(fmt('Greedy cover uses %size% vertices — guaranteed ≤ 2× optimum.', { size: cover.size }),'ok');
  console.log('Greedy 2-approx cover:', [...cover].sort((a,b)=>a-b).join(','), 'size', cover.size);
}
function runOpt(){
  const best=optimumCover(); optSet=best; approxSet=new Set(); render(); updateScores();
  setStatus(fmt('True minimum cover uses %size% vertices (brute force over 2^%length%).', { size: best.size, length: NODES.length }),'ok');
  console.log('Optimum cover:', [...best].sort((a,b)=>a-b).join(','), 'size', best.size);
}
function reset(){ approxSet=new Set(); optSet=new Set(); render(); updateScores();
  setStatus('Run the greedy rule, then find the true optimum.',''); }

document.getElementById('approx').addEventListener('click',runApprox);
document.getElementById('opt').addEventListener('click',runOpt);
document.getElementById('reset').addEventListener('click',reset);
render(); updateScores();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/approximation-algorithms/Content licensed under CC BY-NC 4.0.