Approximation Algorithms & Coping with Hardness

an alpha-approximation guarantee

When we name a specific number for the approximation ratio, we call the algorithm an alpha-approximation, where alpha (the Greek letter) is that number. Saying 'this is a 1.5-approximation' is the contract: feed it any valid input, and the answer it returns will be within a factor of 1.5 of the best possible. The whole point of giving alpha a name is to compare algorithms cleanly — a 1.5-approximation beats a 2-approximation because its worst-case promise is tighter.

Spelling out the contract for the two flavors of problem. For minimization, an alpha-approximation (with alpha >= 1) guarantees ALG <= alpha * OPT for every instance: the cost is at most alpha times optimal. For maximization, it guarantees ALG >= OPT / alpha (equivalently ALG >= (1/alpha) * OPT): the value is at least a 1/alpha fraction of optimal. The subtle and essential part of any such proof is that you never actually know OPT — computing it is the NP-hard task you are avoiding. So the proof works indirectly: you find some quantity you CAN compute that is provably a lower bound on OPT (for minimization) or an upper bound (for maximization), and you bound your algorithm against that surrogate. For vertex cover, for example, the number of edges in a maximal matching is a computable lower bound on the size of any cover.

Two honesty points. First, alpha need not be a constant: for set cover the best guarantee is alpha = ln n, which grows with the input size, and that is provably the best possible unless P = NP. Second, a guarantee is only as good as its proof scope — it holds for the problem and model stated, and an algorithm with a great alpha can still be slow or impractical for other reasons. The guarantee bounds quality, not running time; those are separate promises you check independently.

Christofides' algorithm is a 1.5-approximation for metric TSP: on any instance, the tour it builds has length at most 1.5 times the shortest possible tour. We can prove this without ever computing the true shortest tour, by lower-bounding OPT with a minimum spanning tree.

Alpha names the ratio; the proof bounds the answer against a computable surrogate for OPT.

You almost never compute OPT in an approximation proof — that is the hard problem you are dodging. The trick is to compare your output to a cheap-to-compute bound on OPT, so the guarantee is provable even though OPT itself stays unknown.

Also called
alpha-approximation algorithmfactor-alpha guaranteeα 近似演算法因子 α 保證