Approximation Algorithms

Purpose

When a problem is NP-complete, you give up on computing an exact optimum in polynomial time. This note defines the approximation ratio and derives the guarantees for two standard approximation algorithms: the 2-approximation for vertex cover and the greedy $\ln (n)$ approximation for set cover.

Problems where this comes up include set cover, graph coloring, traveling salesman, maximum independent set, vertex cover, and boolean satisfiability. When your problem reduces to one of these, you have two practical options. Solve the problem exactly on specially structured inputs, or compute a solution with a provable bound on how far it can be from optimal, even in the worst case.

Approximation Ratio

An upper or lower bound on $\alpha$ turns a heuristic into an algorithm you can reason about. For a minimization problem, an $\alpha$-approximation guarantees $OPT\le ALG\le \alpha \cdot OPT$.

Bounding against an unknown OPT

Neither proof below ever computes $OPT$. Each finds a quantity that provably lower-bounds it, the matching size for vertex cover and the $\frac{1}{k}$-coverage argument for set cover, then compares the algorithm’s output to that bound instead.

2-Approximation for Vertex Cover

Problem: find a minimal subset $S$ of vertices in a graph such that every edge has at least one endpoint in $S$.

Algorithm: while some edge $(u,v)$ has neither endpoint in $S$, add both $u$ and $v$ to $S$.

The edges the algorithm picks share no endpoints, so they form a matching $M$. Any vertex cover must contain at least one endpoint of every edge in $M$, and those endpoints are distinct across edges of $M$, so $OPT\ge |M|$. The algorithm outputs $|S|=2|M|$ vertices, which gives

so $\alpha =2$.

Both endpoints, not one

Adding a single endpoint of each uncovered edge loses the guarantee. On a star, picking the leaf endpoint every time collects all $n-1$ leaves while the optimum is the single center. Taking both endpoints is exactly what ties $|S|$ to a matching.

ln(n) Approximation for Set Cover

Problem: given sets $S_1,S_2,\dots ,S_m$ with $S_i\subseteq U$ and $|U|=n$, choose the minimum number of sets that cover all elements of $U$.

Algorithm: while elements remain uncovered, choose the set that covers the most new elements.

Suppose the optimal solution uses $k$ sets. Those $k$ sets cover every remaining element at any point during the run, so some set always covers at least $\frac{1}{k}$ of the remaining elements. The greedy choice covers at least that many. After $t$ steps the number of uncovered elements is at most

Setting $t=k\ln (n)$ drives this below $1$, so greedy selects at most $k\ln (n)$ sets.

Related notes

• greedy algorithms
• linear programming
• interval scheduling and partitioning