Approximation Algorithms

Provably Near-Optimal in Polynomial Time

1:00

When exact is too slow, provably get close — the approximation ratio, vertex cover, set cover, TSP, PTAS/FPTAS, LP rounding, and hardness limits.

By the end, you can

Define the approximation ratio and write the inequality ALG ≤ ρ·OPT for a minimization problem.
Trace the vertex-cover 2-approximation algorithm and reproduce its proof using the maximal matching lower bound.
Explain the greedy set-cover algorithm and state its ln(n) approximation ratio.
Describe why the double-the-MST algorithm for metric TSP achieves ratio 2, and why Christofides achieves 1.5.
Distinguish PTAS from FPTAS and identify knapsack as a problem with an FPTAS.
Explain the LP relaxation + rounding recipe and why rounding at 0.5 preserves feasibility and a factor-2 cost bound.
State what the PCP theorem implies about the limits of approximation for Max-3SAT, set cover, and general TSP.
Distinguish an approximation algorithm (proven guarantee on every input) from a heuristic (no guarantee).

Up next in Advanced Algorithms, Math & PL Theory