Approximation Algorithms

Approximation ratios and provably near-optimal algorithms for NP-hard problems.

The idea

An approximation algorithm solves an optimization problem approximately, in polynomial time, with a proven bound on how far from optimal its answer can be. The need for one arises because many optimization problems are NP-hard: no polynomial-time exact algorithm is known, and we do not expect one to be found.

For a minimization problem, let $\text{OPT}$ be the cost of an optimal solution and $\text{ALG}$ the cost of the solution the algorithm returns. The algorithm is an $\alpha$-approximation, for some $\alpha \ge 1$, when it runs in polynomial time and on every input $\text{ALG} \le \alpha \cdot \text{OPT}.$ The smaller $\alpha$ is, the stronger the promise; $\alpha = 1$ would mean exact.

The obstacle is that $\text{OPT}$ is exactly the quantity we cannot compute — if we could, we would not need the approximation. The analysis therefore never compares $\text{ALG}$ with $\text{OPT}$ directly. Instead it finds a lower bound: a quantity we can reason about that no solution, the optimal one included, can get below. Bounding $\text{ALG}$ above by a multiple of that same quantity then delivers the guarantee. Designing an approximation algorithm is largely the search for a lower bound tight enough to keep the multiple small.

The guarantees differ by problem. Some problems admit a fixed constant factor; for others the best known factor grows with the input size, and for some of those the growth is provably unavoidable unless P $=$ NP.

Ways to work on it

• Walkthrough. The approximation ratio and the 2-approximation for Vertex Cover.
• Practice. Compute an approximation ratio or a matching-based cover size.
• Hardest. The greedy Set Cover analysis and its harmonic-number guarantee.

Not sure where to start? Take the ten-question placement test.