Definition
Constant-factor Approximation Algorithm
A constant-factor approximation algorithm is a polynomial-time approximation algorithm whose guarantee is independent of the input size. For an optimisation problem
with non-negative objective values, it returns a feasible solution on every feasible instance , satisfying: Minimisation
For a minimisation problem and a fixed constant
, Maximisation
For a maximisation problem and a fixed constant
, Under this approximation-ratio convention, a
-approximation for maximisation returns at least half the optimal value. Under the symmetric convention with ratios at least one, the same guarantee is called a factor- approximation.