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
Two common design approaches for 2approx algorithms are greedy methods and linear programming (LP) rounding or
An emblematic 2approx problem is the minimum vertex cover. A simple 2approx algorithm works as follows: compute
Although 2approx algorithms are widely used, not all problems admit a 2-approximation; some have stronger guarantees