2approx

2approx, short for two-approximation, refers to a class of approximation algorithms in combinatorial optimization that guarantee the produced solution is within a factor of 2 of the optimal value. For minimization problems, this means the algorithm returns a solution with cost at most twice the optimum; for maximization problems, the achieved value is at least half of the optimum.

These algorithms are designed for problems where finding the exact optimum is NP-hard, while fast, provable-quality solutions are still valuable. The factor-2 bound is a common target because it is simple to achieve for many problems and often serves as a baseline before attempting tighter guarantees.

Two common design approaches for 2approx algorithms are greedy methods and linear programming (LP) rounding or primal–dual schemes. A typical idea is to build a partial structure that necessarily respects some parts of an optimal solution, then extend it to a full solution with limited overcount.

An emblematic 2approx problem is the minimum vertex cover. A simple 2approx algorithm works as follows: compute a maximal matching M, then take both endpoints of every edge in M as the chosen vertices. The resulting set is a vertex cover of size at most 2|M|. Since any vertex cover must include at least one endpoint from each edge in M, the optimum has size at least |M|, giving a 2-approx bound.

Although 2approx algorithms are widely used, not all problems admit a 2-approximation; some have stronger guarantees or are known to be harder to approximate within a fixed factor. The notion is a central concept in the study of approximation algorithms.