Approximation algorithm

Definition

Consider a minimization problem in which each instance $I$ has a nonempty finite set of feasible solutions. Each feasible solution $S$ has a cost $c(S) > 0$, and $\mathrm{OPT}(I)$ is the least cost of a feasible solution of $I$. Let $\rho \ge 1$ be a real number. A $\rho$-approximation algorithm for the problem is an algorithm $A$ with these properties:

1. $A$ runs in time polynomial in the size of $I$, as for problems in P.
2. For every instance $I$, $A$ outputs a feasible solution $A(I)$.
3. For every instance $I$, $c(A(I)) \le \rho \cdot \mathrm{OPT}(I)$.

For a maximization problem, clause 3 becomes $c(A(I)) \ge \mathrm{OPT}(I) / \rho$. The number $\rho$ is called the approximation ratio of $A$.