An approximate algorithm is a way of dealing with NP-completeness for optimization problem. This technique does not guarantee the best solution. The goal of an approximation algorithm is to come as close as possible to the optimum value in a reasonable amount of time which is at most polynomial time.

Suppose we have some optimization problem instance i, which has a large
number of feasible solutions. Also let *c*(*i*) be the cost of
solution produced by approximate algorithm and *c**(*i*) be the cost
of optimal solution. For minimization problem, we are interested in finding a
solution of a given instance *i* in the set of feasible solutions, such
that *c*(*i*)/*c**(*i*) be as small as possible. On the
other hand, for maximization problem, we are interested in finding a solution in
the feasible solution set such that *c**(*i*)/*c*(*i*) be as
small as possible.

We say that an approximation algorithm for the given problem instance *i*,
has a ratio bound of *p*(*n*) if for any input of sign *n*, the
cost *c* of the solution produced by the approximation algorithm is within
a factor of *p*(*n*) of the cost c* of an optimal solution. That
is

max(*c*(*i*)/*c**(*i*),
*c**(*i*)/*c*(*i*)) ≤ *p*(*n*)

This definition applies for both minimization and maximization problems.

Note that *p*(*n*) is always greater than or equal to 1. If
solution produced by approximation algorithm is true optimal solution then
clearly we have *p*(*n*) = 1.

For a minimization problem, 0 < *c**(*i*) ≤ *c*(*i*),
and the ratio *c*(*i*)/*c**(*i*) gives the factor by which
the cost of the approximate solution is larger than the cost of an optimal
solution. Similarly, for a maximization problem, 0 < *c*(*i*) ≤
*c**(*i*), and the ratio *c**(*i*)/*c*(*i*) gives
the factor by which the cost of an optimal solution is larger than the cost of
the approximate solution.

We define the relative error of the approximate algorithm for any input size as

mod[*c*(*i*) -
*c**(*i*)/ * c**(*i*)]

We say that an approximate
algorithm has a relative bound of ε(*n*) if

mod[*c*(*i*) -
*c**(*i*)/ * c**(*i*)]
≤ ε(*n*)