Approximation algorithm

From Free net encyclopedia

(Difference between revisions)

Revision as of 15:40, 21 April 2006
Andris (Talk | contribs)
sp
Next diff →

Current revision

In computer science, approximation algorithms are an approach to attacking NP-hard optimization problems. Since it is unlikely that there can ever be efficient exact algorithms solving NP-hard problems, one settles for non-optimal solutions, but requires them to be found in polynomial time. Unlike heuristics, which just usually find reasonable good solutions reasonably fast, one wants provable solution quality and provable run time bounds. Ideally, the approximation is optimal up to a small constant factor (say within 5% of the optimal solution).

A typical example for an approximation algorithm is the one for vertex cover in graphs: Find an uncovered edge and add both endpoints to the vertex cover, until none remain. It is clear that the resulting cover is at most twice as large as the optimal one. This is in fact a constant factor approximation algorithm with a factor of 2.

NP-hard problems vary greatly in their approximability; some, such as the bin packing problem, can be approximated to arbitrary factors (such approximation algorithms are often called polynomial time approximation schemes or PTAS). Others are impossible to approximate within any constant (or even polynomial) factor (unless P = NP), such as the maximum clique problem.

Frequently, one can gain approximation algorithms from examining relaxed linear programs.

Not all approximation algorithms are suitable for practical application. For example, most people would not be impressed by a scheme which provably will require them to spend less than twenty times the money that is minimally needed. Also, for some approximation algorithms, the polynomial running time can be quite bad, like O(n²⁰⁰⁰).

Another limitation of the approach is that it applies only to optimization problems and not to "pure" decision problems like satisfiability (although it's often possible to conceive optimization versions of such problems, such as the maximum satisfiability problem).

[edit]

Performance guarantees

For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, for ρ-approximation algorithms it has been proven that the approximation a will not be more (or less, depending on the situation) than a factor ρ times the optimum solution s.

<math>\begin{cases}s \leq a \leq \rho s,\qquad\mbox{if } \rho > 1; \\ \rho s \leq a \leq s,\qquad\mbox{if } \rho < 1.\end{cases}</math>

The factor ρ is called the relative performance guarantee. And approximation algorithms has an absolute performance guarantee or bounded error ε, if it has been proven that

<math> (s - \epsilon) \leq a \leq (s + \epsilon).</math>

Recently, another type of guarantee became popular. The so-called dominance number guarantee. In this type of analysis we ask: how many solutions for the problem is not better than the solution provided by solution of the analyzed approximation algorithm.

[edit]