Skip to main content

Approximation algorithms

An approximation algorithm for an NP-hard optimization problem is a polynomial time feasibility algorithm with some sort of guarantee on the quality of the solution produced by the algorithm. Obviously, we need a way of comparing approximation algorithms and analyzing the quality of the solutions produced by them. Moreover, the “measure of goodness” of a solution produced by an approximation algorithm must somehow relate to the optimum. Such measures are referred to as performance guarantees. The common measure the closeness of a solution to the optimum, the relative performance measure. A relative approximation algorithm computes a solution which is up to r times the optimum in the minimization case and not less than 1/r times the optimum in the maximization case. Such an algorithm is called an r-approximation algorithm.