Approximation Algorithms and Inapproximability
When Exact Optimization Is Too Hard
Motivation
For many NP-hard optimization problems, exact optimal solutions are computationally expensive. Approximation algorithms trade optimality for provable guarantees, often expressed as ratios relative to the optimum.
Approximation Terminology
A PTAS provides what guarantee?
A PTAS gives arbitrarily good approximations for any fixed tolerance .
Correct answer: A approximation for any fixed in polynomial time
Why do approximation algorithms matter for NP-hard problems?
They turn intractable optimization into practically usable algorithms with guarantees.
Correct answer: They provide provable near-optimal solutions when exact optimization is computationally infeasible.
Approximation Algorithm Families
Greedy approximations
- Simple and fast
- Often problem-specific
- Frequently used for covering and scheduling
Relaxation-based methods
- Use LP or SDP relaxations
- Round fractional solutions
- Powerful for combinatorial optimization
Design Pattern for Approximation
-
1
Formulate the optimization problem and identify its hardness.
-
2
Choose a relaxation, greedy rule, or decomposition strategy.
-
3
Prove an approximation ratio using a lower bound on the optimum.
-
4
Analyze running time and scalability.
-
5
Compare the guarantee to known inapproximability barriers.
In approximation analysis, an algorithm with ratio for a minimization problem means what?
For minimization, ratio means the algorithm's cost is at most .
Correct answer: Its output is at most twice the optimal value
Inapproximability
Some problems are not only hard to solve exactly; they are hard to approximate within any meaningful factor under standard assumptions.
Advanced Perspective
Modern approximation theory connects combinatorial optimization, semidefinite programming, probabilistically checkable proofs, and fine-grained hardness. The boundary between tractable approximation and provable impossibility is one of the richest areas in theoretical computer science.