Approximation algorithm

You don't need to be Editor-In-Chief to add or edit content to WikiDoc. You can begin to add to or edit text on this WikiDoc page by clicking on the edit button at the top of this page. Next enter or edit the information that you would like to appear here. Once you are done editing, scroll down and click the Save page button at the bottom of the page.

Please Take Over This Page and Apply to be Editor-In-Chief for this topic: There can be one or more than one Editor-In-Chief. You may also apply to be an Associate Editor-In-Chief of one of the subtopics below. Please mail us [1] to indicate your interest in serving either as an Editor-In-Chief of the entire topic or as an Associate Editor-In-Chief for a subtopic. Please be sure to attach your CV and or biographical sketch.

In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact algorithms solving NP-hard problems, one settles for polynomial time non-optimal solutions. Unlike heuristics, which usually only find reasonably 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 (for instance within 5% of the optimal solution). Approximation algorithms are increasingly being used for problems where exact polynomial-time algorithms are known but are too expensive due to the input size.

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 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 within any factor greater than 1 (such a family of approximation algorithms is often called a polynomial time approximation scheme or PTAS). Others are impossible to approximate within any constant, or even polynomial, factor unless P = NP, such as the maximum clique problem.

NP-hard problems can often be expressed as integer programs (IP) and solved exactly in exponential time. Many approximation algorithms emerge from the linear programming relaxation of the integer program.

Not all approximation algorithms are suitable for all practical applications. They often use IP/LP/Semidefinite solvers, complex data structures or sophisticated algorithmic techniques which lead to difficult implementation problems. Also, some approximation algorithms have impractical running times even though they are polynomial time, for example O(n²⁰⁰⁰). Yet the study of even very expensive algorithms is not a completely theoretical pursuit as they can yield valuable insights. A classic example is the initial PTAS for Euclidean TSP due to Sanjeev Arora which had prohibitive running time, yet within a year, Arora refined the ideas into a linear time algorithm. Such algorithms are also worthwhile in some applications where the running times and cost can be justified e.g. computational biology, financial engineering, transportation planning, and inventory management. In such scenarios, they must compete with the corresponding direct IP formulations.

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).

Performance guarantees

For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, in the case of a ρ-approximation algorithm 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. An approximation algorithm has an absolute performance guarantee or bounded error ε, if it has been proven that

Similarly, the absolute performance ratio Ρ_A of some approximation algorithm A, where I refers to an instance of a problem, and where R_A(I) is the performance guarantee of A on I (i.e. ρ for problem instance I) is:

That is to say that Ρ_A is the largest bound on the approximation ratio, r, that one sees over all possible instances of the problem. Likewise, the asymptotic performance ratio is:

That is to say that it is the same as the absolute performance ratio, with a lower bound n on the size of problem instances. These two types of ratios are used because there exist algorithms where the difference between these two is significant.

Domination analysis provides an alternative way to analyze the quality of an approximation algorithm in terms of the rank of the computed solution in the sorted sequence of all possible solutions.

References

• Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. 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 0-262-03293-7. Chapter 35: Approximation Algorithms, pp.1022–1056.
• Dorit H. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. ISBN 0-534-94968-1. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More

External links

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

WikiDoc Help Menu Quick Start.. Get Started Here! How to Login How to Search Pages How to Start a New Page How to Edit a Page Cheat Sheet Editing basics Learning Basic Formatting How to make Links in WikiDoc & to External Sites How to Make Lists How to Ignoring Formatting Adding References or Footnotes to Articles Tracking Changes You Have Made How to Put an Article Into a Category When Multiple Topics Should Go To The Same Page (MI, Acute MI, AMI) Using Redirection Advanced editing How to Make Tables How to Insert Images and Other Media How to Add Video Help:How to Make Columns Web Colors How To Make Templates How to Move Pages Inserting Dynamic Dates and Times Inserting WikiDoc Statistics Editing the Table of Contents Communicating your edits Let others know what you changed: The importance of Edit Summaries Minor Edits Edit Conflicts Help Videos You Can Watch Getting Started Video

cs:Aproximační algoritmy de:Approximationsalgorithmus fr:Algorithme d'approximation ko:근사 알고리즘 he:אלגוריתם קירוב ja:近似アルゴリズムth:ขั้นตอนวิธีการประมาณ