Approximation Algorithms & Ratio

Provable closeness to optimum: ratio, the matching bound, and the integrality gap.

The idea

An approximation algorithm answers an optimization problem that has no known fast exact algorithm: it runs fast and returns a solution provably close to the best possible.

Fix a minimization problem. On an instance, write $\mathrm{OPT}$ for the cost of an optimal solution and $\mathrm{ALG}$ for the cost of the solution the algorithm returns. The algorithm is a $k$-approximation, for a ratio $k \ge 1$, if on every instance it returns a feasible solution with

$\mathrm{ALG} \le k \cdot \mathrm{OPT}.$

This is a worst-case promise, not a typical-case one, and the closer $k$ is to $1$ the stronger it is.

Proving the promise appears circular, since $\mathrm{OPT}$ is exactly the quantity we cannot compute. The standard escape is a computable lower bound: find a quantity $B$ that we can compute and that satisfies $B \le \mathrm{OPT}$, then bound the output against $B$ instead. If the algorithm guarantees $\mathrm{ALG} \le k B$, then $\mathrm{ALG} \le k \cdot \mathrm{OPT}$ follows, and the optimum itself never has to be found. Most approximation guarantees rest on a lower bound of this kind.

Ways to work on it

• Walkthrough. The k-approximation guarantee and the Vertex Cover 2-approximation.
• Practice. Compute approximation ratios and matching-based bounds.
• Hardest. The integrality gap as a barrier to the provable ratio.

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