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). Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... In computer science, an optimization problem is the problem to find among all feasible solutions for some problem the best one. ... In computational complexity theory, Polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... In computer science, besides the common use as rule of thumb (see heuristic), the term heuristic has two well-defined technical meanings. ...

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. In computer science, the vertex cover problem or node cover problem is an NP-complete problem in complexity theory, and was one of Karps 21 NP-complete problems. ... In complexity theory the class APX (an abbreviation of approximable) is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor approximation algorithms for short). ...

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. In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. ... In computer science, a polynomial time approximation scheme (abbreviated PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). ... In computational complexity theory, the clique problem or k-clique problem is a graph-theoretical NP-complete problem. ...

Frequently, one can gain approximation algorithms from examining relaxed linear programs. In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ...

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 run 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). In computer science, an optimization problem is the problem to find among all feasible solutions for some problem the best one. ... The Boolean satisfiability problem (SAT) is a decision problem considered in complexity theory. ... The Maximum Satisfiability problem (MAX-SAT), an FNP generalization of Satisfiability problem (SAT), asks for the maximum number of clauses which can be satisfied by any assignment. ...

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.

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

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. This article or section contains information that has not been verified and thus might not be reliable. ...

References

• Vijay V. Vazirani. Approximation Algorithms. ISBN 3540653678.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter 35: Approximation Algorithms, pp.1022–1056.

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

External links

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems.