introduction to approximation algorithms

 

Let P be an optimization problem.
For every input x of P, let OP T(x) denote the optimal value of the solution for x.
Let A be an algorithm and c a constant such that c ≥ 1.
1. Suppose P is a minimization problem. We say that A is a c-approximation for P
if for every input x of P: OP T(x) ≤ A(x) ≤ c · OP T(x)
2. If P is a maximization problem. We say that A is a c-approximation for P if for every input x of P: OP T(x)/ c ≤ A(x) ≤ OP T(x) In both cases, we call c the approximation ratio of A.