• Overview
• Details
• Exercises

Approximation algorithms provide provable guarantees for hard optimization problems. They run in polynomial time and return solutions within a factor of optimal, using techniques like greedy methods, local search, LP relaxations/rounding, and primal–dual frameworks.

• Approximation ratio: For minimization, ALG ≤ α · OPT; for maximization, ALG ≥ OPT/α.
• Greedy set cover achieves H_n ≈ ln n factor via charging analysis.
• 2-approx for metric TSP via MST doubling + shortcutting (triangle inequality) or Christofides' 3/2-approx (outline).
• 2-approx for vertex cover via maximal matching; local-ratio and primal–dual interpretations.
• LP relaxation and rounding: facility location, set cover; integrality gap and performance bounds.
• PTAS/FPTAS: e.g., knapsack FPTAS via scaling; PTAS for Euclidean TSP (high-level).

1. Prove the harmonic-number H_n bound for greedy set cover using a charging scheme.
2. Give a 2-approximation for vertex cover using maximal matching and prove the guarantee.
3. Design an LP relaxation and a rounding scheme for a simple facility location instance; analyze the ratio.