Lecture 17: Complexity - Approximation Algorithms

What this lecture covers

This MIT 6.046 lecture answers what to do once a problem is known to be NP-complete: instead of giving up on polynomial time entirely, design a heuristic and prove it always stays within a bounded factor of the optimal answer. It introduces the vocabulary of approximation ratios, approximation schemes, PTAS, and FPTAS, then works through provable approximation algorithms for three classic NP-hard problems.

The lecture follows directly from the previous lecture's introduction to NP-completeness and reductions, and precedes a second lecture on approximation. After watching, you should be able to define an approximation ratio, distinguish a constant-factor approximation from one that grows with input size, and reproduce the proofs that a maximal-matching heuristic gives a 2-approximation for vertex cover, a greedy heuristic gives a logarithmic approximation for set cover, and a seeded greedy algorithm gives a PTAS for partition.

Key ideas

• Approximation ratio rho(n): bounds how far an algorithm's cost C can be from the optimal cost C_opt, expressed so it works for both minimization and maximization problems.
• Approximation algorithm vs. scheme: an algorithm has a fixed ratio, while a scheme takes an extra parameter epsilon and can be tuned to get arbitrarily close to 1 + epsilon at the cost of more runtime.
• PTAS: polynomial in the input size n for any fixed epsilon, but not necessarily polynomial in 1/epsilon.
• FPTAS: polynomial in both n and 1/epsilon, a stronger and rarer guarantee.
• Vertex cover by maximal matching: repeatedly pick any remaining edge, add both endpoints to the cover, and discard incident edges; this is always within a factor of 2 of optimal because the chosen edges are disjoint and each needs its own cover vertex.
• Set cover by greedy largest-subset selection: repeatedly pick the subset covering the most remaining elements; the pigeonhole principle bounds how fast the uncovered set can shrink, giving an O(log n) approximation.
• Partition PTAS: exhaustively find the optimal split of the m heaviest items, then greedily assign the rest to whichever side currently weighs less; increasing m (equivalently, decreasing epsilon) trades runtime for closeness to optimal.

Walkthrough

Approximation algorithms and schemes (0:00)

The lecture frames approximation as one response to discovering a problem is NP-complete: rather than an unproven heuristic, prove a bound on how far the heuristic's output can be from optimal. It defines the approximation ratio rho(n) and distinguishes constant-factor ratios from ones that grow with n, then introduces approximation schemes, which take a tunable epsilon and trade runtime for accuracy. A PTAS is polynomial in n for fixed epsilon but not necessarily in 1/epsilon; an FPTAS is polynomial in both.

Vertex cover via the maximum-degree heuristic (12:16)

Vertex cover asks for the smallest set of vertices touching every edge. The lecture first tries the intuitive heuristic of repeatedly picking the highest-degree vertex, and constructs a pathological example (a layered graph with K! vertices) where this heuristic's cover can be roughly log K times larger than optimal, showing the approximation ratio grows with the input size rather than staying constant.

Vertex cover by maximal matching, proved as a 2-approximation (25:24)

A simpler heuristic instead repeatedly picks any remaining edge, adds both endpoints to the cover, and removes all edges touching those two vertices, repeating until no edges remain. The key observation is that the picked edges never share a vertex, so if a edges are picked, the cover has size 2a. Since covering those a disjoint edges requires at least one distinct vertex per edge in any valid cover, the optimal cover size is at least a, giving C <= 2 * C_opt: a constant-factor 2-approximation regardless of the graph.

Set cover and the greedy logarithmic bound (35:43)

Set cover asks for the fewest subsets from a given family whose union covers a target set X. The greedy heuristic repeatedly picks the subset covering the most currently-uncovered elements. The proof assumes an optimal cover of size T and shows, via the pigeonhole principle, that at each step at least one of the T optimal subsets must cover at least a 1/T fraction of what remains, so the greedy choice covers at least that much too. This gives a shrinking recurrence for the uncovered set size, which resolves into a bound of k/T <= ln(n) + 1, meaning the greedy algorithm never uses more than roughly T * ln(n) sets.

Partition and its trivial 2-approximation (57:11)

Partition asks for a split of weighted items into two sets A and B minimizing the larger of the two total weights. Since the sum of all weights is 2L, the optimal solution is at least L, and simply dumping everything into one set gives a trivial 2-approximation. The lecture treats this as a starting point before building a tunable scheme.

The partition PTAS: seeding and greedy assignment (1:01:12)

The PTAS sorts items by weight, then exhaustively searches all 2^m partitions of just the m largest items to find an optimal seed split (A', B'), where m relates to epsilon by roughly epsilon = 1/(m+1). The remaining n - m items are then assigned greedily, one at a time, to whichever of A or B currently has less weight. The exhaustive phase costs O(2^m), making the scheme a PTAS (polynomial in n, exponential in 1/epsilon) rather than an FPTAS.

Proving the PTAS's approximation ratio (1:07:17)

The proof looks at the last element K added to the heavier final set A. If K was added during the exhaustive seeding phase, then A never changed afterward and equals the optimal split for the m-item subproblem, giving an approximation ratio of exactly 1. If K was added during the greedy phase, the fact that it was placed in A means A (before adding K) was no heavier than B, which combined with the sorted-order assumption (SK is at most as large as any of the m largest items) bounds SK relative to 2L. Working through the algebra gives a final ratio of 1 + 1/(m+1) = 1 + epsilon, confirming the scheme meets its target for any chosen m.

Before you watch

• Review NP-completeness and NP-hardness definitions from the preceding lecture, since this lecture assumes vertex cover, set cover, and partition are already known to be NP-hard.
• Recall the pigeonhole principle, used directly in the set cover proof.
• Basic comfort manipulating inequalities and summations will help with the partition PTAS derivation.

Check your understanding

1. Why does the maximum-degree heuristic for vertex cover fail to give a constant-factor approximation, while the maximal-matching heuristic succeeds?
2. In the vertex cover proof, why does the fact that picked edges are disjoint guarantee that the optimal cover size is at least as large as the number of picked edges?
3. How does the pigeonhole principle justify that the greedy set-cover choice removes at least a 1/T fraction of the remaining uncovered elements?
4. In the partition PTAS, what determines the tradeoff between runtime and how close the algorithm gets to 1 + epsilon?
5. Why does the partition PTAS's approximation ratio become exactly 1 when the last element added to the heavier set was chosen during the exhaustive seeding phase rather than the greedy phase?