Constant-factor Approximation Algorithm

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 $\Pi$ with non-negative objective values, it returns a feasible solution $A(I)$ on every feasible instance $I$, satisfying:

Minimisation

For a minimisation problem and a fixed constant $c\ge 1$,

$$\mathrm{OPT}(I)\le f_{\Pi }(I,A(I))\le c\mathrm{OPT}(I).$$

Maximisation

For a maximisation problem and a fixed constant $0<\alpha \le 1$,

$$\alpha \mathrm{OPT}(I)\le f_{\Pi }(I,A(I))\le \mathrm{OPT}(I).$$

Under this approximation-ratio convention, a $0.5$-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-$2$ approximation.