Approximation Algorithms — Importance & Vertex Cover Application

(i) Approximation Algorithms

Polytime algorithms that produce feasible solution with proven distance from optimum. For minimization minimization: $ALG ≤ ρ·OPT$; for maximization $OPT ≤ ρ·ALG$; $ρ≥1$ approximation ratio (performance guarantee). Contrasts with heuristics (no guarantee).

Examples: Metric TSP 2-approx (MST doubling), Christofides 1.5, Set Cover $\ln n$, Knapsack FPTAS.

(ii) Importance for NP-Hard Optimization

• Exact polytime impossible unless $P=NP$ → need alternative for large instances.
• Provides usable solution with confidence bound; helps decide tradeoff speed vs quality.
• Underpins theoretical classification: APX, PTAS, FPTAS hierarchy shows which problems approximable arbitrarily well.
• Guides practice: if problem hard to approximate (e.g., Clique within $n^{1-ε}$ hard), don't waste effort seeking good approx; use heuristic/exponential exact for moderate $n$.

Without approximation, only brute $O(2^n)$ exact feasible for tiny $n$; approximation scales to thousands.

(iii) Applied to Vertex Cover

Minimum Vertex Cover: min vertices covering all edges — NP-hard (reduction from 3-SAT).

2-Approximation (as in Q84/Q97):

C=∅; E' =E
while E'≠∅: pick any (u,v)∈E'; C∪={u,v}; remove all edges incident to u or v

Matching $M$ picked disjoint → $OPT ≥|M|$ (need one per edge) → $|C|=2|M| ≤2 OPT$ → ratio2.

Example: Path $a-b-c-d$. Pick $(a,b)$ → $C={a,b}$, remove edges $ab,bc$ → remaining $c-d$ → pick $(c,d)$ → $C={a,b,c,d}$ size4 vs OPT2 ($b,c$) → ratio2 tight for path? star gives ratio2 worst.

Hardness: Assuming Unique Games, no polytime $(2-ε)$ approx for vertex cover — so this simple 2-approx is essentially best possible.

Thus approximation bridges intractability and practical need.