2Approximation

2-Approximation is a term used in the field of approximation algorithms to describe a class of algorithms that guarantee a solution within a factor of two of the optimum for certain optimization problems. In minimization problems, a 2-approximation algorithm outputs a solution whose objective value is at most twice the optimal value. In maximization problems, a 2-approximation guarantees a solution whose value is at least half of the optimum.

A classic example is the Vertex Cover problem. A simple 2-approximation works by finding a maximal matching in the input graph and then taking both endpoints of every edge in the matching as the vertex cover. The resulting set has size at most 2 times the size of an optimal vertex cover, since every edge of the matching must be covered and the matching contains at most OPT edges.

2-approximation algorithms often arise from straightforward greedy procedures, or from linear programming relaxations followed by rounding. For Vertex Cover, the linear programming formulation is half-integral, and a standard rounding yields the 2-approx guarantee. Many problems in combinatorial optimization admit constant-factor approximations, among which 2-approximations are particularly simple and well studied.

Limitations include that not all problems admit a 2-approximation, and for some problems, achieving a factor better than 2 is NP-hard or known to be unlikely under standard complexity assumptions. In the broader taxonomy, 2-approximation algorithms are part of a spectrum of approximation guarantees, sitting alongside other constant-factor and asymptotic guarantees such as PTAS and APX.