Approximation for NP-Hard Optimization — General Steps + Example

Why Approximation?

NP-hard optimization (e.g., TSP, Vertex Cover, Set Cover, Knapsack) no known polytime exact solution (if $P
eq NP$). Approximation algorithms give near-optimal feasible solution in polytime with proven ratio guarantee.

General Steps

1. Formulate optimization: Min or Max objective (e.g., min vertex cover size, min tour length).
2. Check complexity: Prove NP-hard (reduction from known NP-hard). → motivates approximation.
3. Design polytime heuristic: Often greedy, DP relaxation, LP rounding, MST/matching, local search.
4. Prove approximation ratio $\rho$:
   • For minimization: $\frac{ALG}{OPT} \le \rho$
   • For maximization: $\frac{OPT}{ALG} \le \rho$
     Show bound via lower bound on OPT (e.g., LP optimum ≤ OPT, MST ≤ TSP OPT) and upper bound on ALG.
5. Analyze time: Must be polytime (e.g., $O(n\log n)$, $O(n^3)$).
6. Tighten: Improve ratio or show hardness of better approximation (inapproximability).

Example: Minimum Vertex Cover — 2-Approximation

Input graph $G(V,E)$, goal min vertices covering all edges.

Algorithm (matching-based, as in Q84):

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

Proof of ratio 2: Let $M$ be set of edges picked (matching, disjoint). Any vertex cover must include ≥1 endpoint per edge in $M$ → $OPT ≥ |M|$. Algorithm includes both endpoints → $|C|=2|M| ≤2·OPT$.

Example graph: Triangle $a-b, b-c, c-a$. $M$ picks $(a,b)$ → $C={a,b}$ size2, OPT=2 (any 2 cover) ratio1. Star center+leaves: picks center-leaf → $C$ size2 vs OPT1 → ratio2 tight.

Time $O(V+E)$.

Other examples: Metric TSP 2-approx via MST (Q96), Knapsack FPTAS, Set Cover $\ln n$ greedy.

Importance: Provides usable solutions with guarantee where exact is infeasible.