Intuition The big pictureMany problems we care about are NP-hard — we believe no algorithm solves them exactly in polynomial time. But we still need answers . The trick: stop demanding the perfect answer. Instead, run fast and guarantee the answer is "not too far" from optimal. An approximation algorithm is a polynomial-time algorithm that comes with a provable guarantee on how bad it can be.
The key insight that makes this possible : even when we can't find the optimum OPT, we can often find a cheap lower/upper bound on OPT and compare our solution to that bound instead of to OPT itself.
Definition Approximation ratioLet OPT \text{OPT} OPT ALG \text{ALG} ALG
For a minimization problem, ALG \text{ALG} ALG ρ \rho ρ every input:
ALG OPT ≤ ρ , ρ ≥ 1 \frac{\text{ALG}}{\text{OPT}} \le \rho, \qquad \rho \ge 1 OPT ALG ≤ ρ , ρ ≥ 1
For a maximization problem:
ALG OPT ≥ ρ , ρ ≤ 1 \frac{\text{ALG}}{\text{OPT}} \ge \rho, \qquad \rho \le 1 OPT ALG ≥ ρ , ρ ≤ 1 ρ ≥ 1 \rho\ge 1 ρ ≥ 1 OPT / ALG \text{OPT}/\text{ALG} OPT / ALG
ρ \rho ρ worst-case ratio over all inputs. Smaller-but-≥ 1 \ge 1 ≥ 1 ρ = 1 \rho=1 ρ = 1
Intuition WHY compare to a bound, not to OPT?We can't compute OPT (that's the whole problem!). So in every minimization proof you'll see this pattern. Find a lower bound LB \text{LB} LB LB ≤ OPT \text{LB}\le\text{OPT} LB ≤ OPT ρ \rho ρ that bound :
ALG ≤ ρ ⋅ LB ≤ ρ ⋅ OPT . \text{ALG} \le \rho\cdot\text{LB} \le \rho\cdot\text{OPT}. ALG ≤ ρ ⋅ LB ≤ ρ ⋅ OPT . directly about your algorithm; the second is free because LB ≤ OPT \text{LB}\le\text{OPT} LB ≤ OPT
Given graph G = ( V , E ) G=(V,E) G = ( V , E ) smallest set C ⊆ V C\subseteq V C ⊆ V C C C
Algorithm (Maximal Matching based):
C ← ∅ C\leftarrow\varnothing C ← ∅ While there is an uncovered edge ( u , v ) (u,v) ( u , v ) both u u u v v v C C C u u u v v v
Return C C C
Worked example Why does this give ratio 2? (Derivation from scratch)The edges ( u , v ) (u,v) ( u , v ) picked in step 2 form a matching M M M ( u , v ) (u,v) ( u , v )
Why this step? Two facts (here the lower bound is LB = ∣ M ∣ \text{LB}=|M| LB = ∣ M ∣
Lower bound on OPT: any vertex cover must cover each edge of M M M M M M one distinct vertex per matched edge . So LB = ∣ M ∣ ≤ OPT \text{LB}=|M|\le\text{OPT} LB = ∣ M ∣ ≤ OPT Upper bound on ALG: we added exactly 2 vertices per matched edge, so ALG = 2 ∣ M ∣ = 2 LB \text{ALG}=2|M|=2\,\text{LB} ALG = 2∣ M ∣ = 2 LB
Combine in the standard pattern:
ALG = 2 ∣ M ∣ = 2 LB ≤ 2 ⋅ OPT . \text{ALG}=2|M| = 2\,\text{LB}\le 2\cdot\text{OPT}. ALG = 2∣ M ∣ = 2 LB ≤ 2 ⋅ OPT . ρ = 2 \rho=2 ρ = 2 2-approximation , and notice we never computed OPT — only the lower bound ∣ M ∣ |M| ∣ M ∣
Cities with distances satisfying the triangle inequality d ( a , c ) ≤ d ( a , b ) + d ( b , c ) d(a,c)\le d(a,b)+d(b,c) d ( a , c ) ≤ d ( a , b ) + d ( b , c )
Algorithm (Double-tree):
Build a Minimum Spanning Tree T T T
Do a DFS/Euler walk of T T T = 2 ⋅ cost ( T ) =2\cdot\text{cost}(T) = 2 ⋅ cost ( T )
Shortcut repeated cities (skip already-visited) → a valid tour.
Worked example Derivation of ratio 2Here the lower bound is LB = cost ( T ) \text{LB}=\text{cost}(T) LB = cost ( T )
Lower bound: delete one edge from any optimal tour → a spanning tree (a path is a tree). So LB = cost ( T ) ≤ OPT \text{LB}=\text{cost}(T)\le \text{OPT} LB = cost ( T ) ≤ OPT cheapest tree.)
Why this step? OPT visits all vertices; removing one edge keeps it connected & acyclic on all vertices = a spanning tree, which is ≥ \ge ≥ minimum spanning tree.
Doubling: Euler walk costs 2 cost ( T ) = 2 LB 2\,\text{cost}(T)=2\,\text{LB} 2 cost ( T ) = 2 LB
Shortcutting: by triangle inequality, skipping a vertex never increases cost.
Why this step? Going a → b → c a\to b\to c a → b → c a → c a\to c a → c ≤ \le ≤
Therefore ALG ≤ 2 cost ( T ) = 2 LB ≤ 2 OPT \text{ALG}\le 2\,\text{cost}(T)=2\,\text{LB}\le 2\,\text{OPT} ALG ≤ 2 cost ( T ) = 2 LB ≤ 2 OPT 3 / 2 3/2 3/2
Assign n n n m m m makespan (max load).
Worked example Greedy + the two lower boundsGreedy: put each job on the currently least-loaded machine.
Let machine i i i L L L j j j t j t_j t j j j j i i i minimum , so all machines had load ≥ L − t j \ge L-t_j ≥ L − t j ∑ k t k ≥ m ( L − t j ) ⇒ L − t j ≤ 1 m ∑ t k . \sum_k t_k \ge m(L - t_j)\;\Rightarrow\; L - t_j \le \tfrac1m\sum t_k. ∑ k t k ≥ m ( L − t j ) ⇒ L − t j ≤ m 1 ∑ t k .
OPT ≥ 1 m ∑ t k \text{OPT}\ge \frac1m\sum t_k OPT ≥ m 1 ∑ t k someone gets at least the average).OPT ≥ max k t k ≥ t j \text{OPT}\ge \max_k t_k \ge t_j OPT ≥ max k t k ≥ t j somewhere ).
So L = ( L − t j ) + t j ≤ OPT + OPT = 2 OPT L = (L-t_j) + t_j \le \text{OPT}+\text{OPT}=2\,\text{OPT} L = ( L − t j ) + t j ≤ OPT + OPT = 2 OPT two lower bounds and added them — same spirit: bound everything from below by OPT.)
Common mistake Steel-manning the common errorsMistake A: "A 2-approximation means I'm right 50% of the time / wrong by 50%."
Why it feels right: "2" sounds like a percentage. Fix: it means cost ≤ 2 × \le 2\times ≤ 2 × worst case , always, deterministically — not a probability. Usually you're much closer than 2 × 2\times 2 ×
Mistake B: "To prove the ratio I must know OPT."
Why it feels right: the ratio literally contains OPT. Fix: you compare against a lower bound LB ≤ OPT \text{LB}\le\text{OPT} LB ≤ OPT ALG ≤ ρ LB \text{ALG}\le\rho\,\text{LB} ALG ≤ ρ LB LB ≤ OPT \text{LB}\le\text{OPT} LB ≤ OPT
Mistake C: Using the MST-double-tree on non-metric TSP.
Why it feels right: the algorithm runs fine. Fix: shortcutting needs the triangle inequality; without it the bound collapses, and general TSP has no constant-factor approximation (unless P=NP).
Mistake D: For maximization, writing ALG / OPT ≤ ρ \text{ALG}/\text{OPT}\le\rho ALG / OPT ≤ ρ Fix: maximization ratios bound from below : ALG ≥ ρ OPT \text{ALG}\ge \rho\,\text{OPT} ALG ≥ ρ OPT ρ ≤ 1 \rho\le 1 ρ ≤ 1
Recall Active recall — cover the answers
What does a 2-approximation guarantee ?
In Vertex Cover, why is OPT ≥ ∣ M ∣ \text{OPT}\ge |M| OPT ≥ ∣ M ∣
In Metric TSP, why is cost(MST) ≤ OPT \text{cost(MST)}\le \text{OPT} cost(MST) ≤ OPT
Which property lets shortcutting not increase cost?
What's the difference between PTAS and FPTAS?
Recall Feynman: explain to a 12-year-oldImagine packing a backpack the perfect way takes forever. Instead you use a quick rule of thumb. You can't tell exactly how good the perfect packing is — but you can find a floor : "the perfect packing needs at least this much space." Then you show "my quick way uses at most twice that floor." Since the perfect answer is above the floor too, my quick answer is at most twice the perfect one. That promise — without ever knowing the perfect answer — is the approximation ratio.
Mnemonic Remember the proof pattern"LB-LADDER": ALG ≤ ρ ⋅ LB ≤ ρ ⋅ OPT \text{ALG}\le \rho\cdot\text{LB}\le \rho\cdot\text{OPT} ALG ≤ ρ ⋅ LB ≤ ρ ⋅ OPT ρ \rho ρ Lower Bound . Step 2: that LB is ≤ \le ≤ Matching, MST, Average .
NP-completeness — why we approximate at all.Vertex Cover · Maximum Matching — the 2-approx lower bound.Minimum Spanning Tree — bound for Metric TSP.Greedy Algorithms — load balancing.PTAS and FPTAS · Inapproximability / PCP theorem .Triangle Inequality — enables shortcutting.
What is an approximation ratio for a minimization problem? The worst-case ratio ALG/OPT ≤ ρ (ρ≥1) over all inputs; ρ=1 is exact.
Why can we prove ratios without knowing OPT? Find a lower bound LB ≤ OPT (matching size, MST cost, average load), prove ALG ≤ ρ·LB, then ALG ≤ ρ·LB ≤ ρ·OPT.
Vertex Cover 2-approx: what is the algorithm? Repeatedly pick any uncovered edge, add BOTH endpoints to the cover, remove incident edges.
Why is OPT ≥ |M| in the Vertex Cover proof? The picked edges form a matching; each disjoint edge needs ≥1 distinct cover vertex, so OPT ≥ matching size.
Why is ALG = 2|M| in Vertex Cover? We add exactly 2 vertices per matched edge.
Metric TSP double-tree: lower bound on OPT? Removing one edge from an optimal tour gives a spanning tree, so cost(MST) ≤ OPT.
Why does shortcutting not increase tour cost? Triangle inequality: skipping a city (a→c instead of a→b→c) costs ≤ the detour.
Load balancing greedy ratio and why? 2; because OPT ≥ average load and OPT ≥ max job size, and L ≤ (L−t_j)+t_j ≤ 2·OPT.
Difference between PTAS and FPTAS? Both give (1+ε)-approx; FPTAS runs in time polynomial in n AND 1/ε, PTAS only in n (can be exponential in 1/ε). Every FPTAS is a PTAS.
Does general (non-metric) TSP have a constant-factor approximation? No (unless P=NP).
Common myth about "2-approximation"? It is NOT a probability/percentage; it's a deterministic worst-case bound: ALG ≤ 2·OPT always.
lower bound LB = size of M le OPT
adds 2 verts per edge, ALG = 2 times size of M
Bound on OPT, not OPT itself
Maximal matching algorithm
Intuition Hinglish mein samjhoDekho, kuch problems (jaise Vertex Cover, TSP) NP-hard hote hain — matlab exact best answer fast nikalna almost impossible. Toh hum perfectionism chhod dete hain. Approximation algorithm fast chalta hai aur ek guarantee deta hai: "mera answer optimal se zyada se zyada itna hi bura hoga." Yeh "itna bura" wala factor hi approximation ratio hai. 2-approximation ka matlab: cost kabhi bhi optimal ke double se zyada nahi — har input pe, hamesha (yeh probability nahi hai bhai, worst-case guarantee hai).
Sabse mast trick: hume OPT pata hi nahi hota (wahi toh problem hai!). Toh hum ek lower bound (LB) dhundhte hain jo OPT se chhota ya barabar ho. Phir do step: (1) prove karo ki ALG ≤ ρ·LB, aur (2) kyunki LB ≤ OPT, automatically ALG ≤ ρ·LB ≤ ρ·OPT. Vertex Cover mein LB = matching size |M| — har disjoint edge ko cover karne ke liye kam se kam 1 vertex chahiye, toh |M| ≤ OPT. Aur hum har matched edge ke dono endpoints daalte hain, toh ALG = 2|M| = 2·LB ≤ 2·OPT. OPT ko jaane bina ratio prove ho gaya!
Yahi LB-LADDER pattern har minimization proof mein milega: pehle apne algorithm ko ρ times ek Lower Bound se compare karo, phir woh LB OPT se chhota hai toh free mein OPT tak pahunch jaao. Metric TSP mein LB = MST ka cost (tour se ek edge hatao toh spanning tree, toh MST ≤ OPT). Load balancing mein do lower bounds — average load aur biggest job — dono ko jodke 2·OPT mil jata hai. Teen yaad rakho: Matching, MST, Average .
Yaad rakhna: "2-approx" matlab 50% chance ya 50% galat nahi hota. Aur non-metric (bina triangle inequality) TSP pe shortcutting wala trick mat lagana — general TSP ka koi constant-factor approximation hota hi nahi (jab tak P=NP na ho).
