Algorithms
Approximation Algorithms
Difficulty: Advanced
Vertex Cover is NP-hard: there is no known polynomial algorithm that finds a minimum cover. But a five-line greedy algorithm guarantees a cover whose size is at most twice the minimum, and the proof fits on a napkin. That guarantee, the...
Approximation Algorithms
Vertex Cover is NP-hard: there is no known polynomial algorithm that finds a minimum cover. But a five-line greedy algorithm guarantees a cover whose size is at most twice the minimum, and the proof fits on a napkin. That guarantee, the approximation ratio, is the difference between a heuristic that might be terrible and an algorithm with a written contract about how far from optimal its answer can be.
Approximation Algorithms introduces that contract-based view of NP-hard optimization. You will define approximation ratio formally and walk through the classic constant-factor algorithms: a 2-approximation for Vertex Cover via greedy maximal matching, an O(log n)-approximation for Set Cover via greedy element-counting, and a 2-approximation for Metric TSP that exploits the triangle inequality on top of an MST. The lesson then covers approximation schemes (PTAS, polynomial in n for any fixed epsilon; FPTAS, polynomial in both), with Knapsack FPTAS as the canonical example. Throughout, the lesson contrasts approximation algorithms with heuristics, where heuristics give no guarantee at all.
In Greedy (Intro), you saw simple greedy strategies and their correctness proofs. Dynamic Programming (Advanced) introduced 0/1 Knapsack as an NP-hard exact algorithm. This lesson asks the next question: when exact is too slow, how close to optimal can we provably get?
Next, Advanced Bit Manipulation turns to bit-level tricks for O(1) and bitmask-DP solutions.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Define approximation ratio and distinguish between constant-factor, logarithmic, and polynomial-time approximation schemes.
Implement a 2-approximation algorithm for Vertex Cover using maximal matching.
Implement the greedy O(log n)-approximation for Set Cover.
Explain the 2-approximation for Metric TSP using MST doubling.
Describe the Knapsack FPTAS and explain why it achieves (1+epsilon)-approximation in polynomial time.
Why This Matters
01
Many real-world optimization problems (scheduling, routing, resource allocation) are NP-hard. Approximation algorithms give you polynomial-time solutions with guaranteed quality bounds.
02
The 2-approximation for Vertex Cover demonstrates that greedy matching can achieve provably good results with very simple code -- a powerful lesson in algorithm design.
03
The Knapsack FPTAS shows that some NP-hard problems can be solved to any desired accuracy in polynomial time -- a surprising and practically important result.
04
Understanding approximation ratios is essential for system design interviews where you must justify why a heuristic is good enough for production use.
Key Terms
6 terms you'll encounter in this lesson
Approximation Ratio
For a minimization problem, the approximation ratio r means the algorithm's solution is at most r times the optimal. For maximization, the solution is at least 1/r times optimal. A 2-approximation for min Vertex Cover returns a cover of size at most 2 * OPT.
NP-Hard
A problem is NP-hard if every problem in NP can be reduced to it in polynomial time. No polynomial-time exact algorithm is known (and none likely exists). Examples: TSP, Vertex Cover, Set Cover, Knapsack.
PTAS (Polynomial Time Approximation Scheme)
A family of algorithms parameterized by epsilon > 0 that achieve (1+epsilon)-approximation. The running time is polynomial in n but may be exponential in 1/epsilon.
FPTAS (Fully Polynomial Time Approximation Scheme)
Like PTAS, but the running time is polynomial in both n AND 1/epsilon. The Knapsack problem has an FPTAS. Only a few NP-hard problems have one.
Maximal Matching
A matching (set of non-adjacent edges) that cannot be extended by adding another edge. Used as the basis for the 2-approximation of Vertex Cover: the endpoints of a maximal matching form a vertex cover.
Set Cover
Given a universe U and a collection of subsets, find the minimum number of subsets whose union equals U. The greedy algorithm (always pick the set covering the most uncovered elements) achieves an O(log n) approximation.
Heads Up
Common misconceptions to watch out for
"Approximation algorithms are just heuristics"
Heuristics have no performance guarantee. Approximation algorithms come with a provable bound on how far the solution can be from optimal. A 2-approximation for Vertex Cover guarantees the answer is at most 2x optimal, no matter the input.
"All NP-hard problems are equally hard to approximate"
Some NP-hard problems can be approximated within a constant factor (Vertex Cover: 2x), some only logarithmically (Set Cover: O(log n)x), and some cannot be approximated within any constant factor unless P=NP (general TSP). The hardness of approximation varies greatly.
"FPTAS solves NP-hard problems in polynomial time"
FPTAS finds a (1+epsilon)-approximate solution in polynomial time, not the exact optimal. For any fixed epsilon > 0, you get a solution within (1+epsilon) of optimal. Getting the exact answer (epsilon=0) would require solving the NP-hard problem exactly.