Editing Approximation algorithm (section)

{{Short description|Class of algorithms that find approximate solutions to optimization problems}}
In [[computer science]] and [[operations research]], '''approximation algorithms''' are [[Time complexity#Polynomial time|efficient]] [[algorithm]]s that find [[approximation|approximate]] solutions to [[optimization problem]]s (in particular [[NP-hardness|NP-hard]] problems) with provable guarantees on the distance of the returned solution to the optimal one.<ref name="Bernard. 2011">{{Cite book|title=The design of approximation algorithms|last=Bernard.|first=Shmoys, David|date=2011|publisher=Cambridge University Press|isbn=9780521195270|oclc=671709856|url=http://www.designofapproxalgs.com/}}</ref> Approximation algorithms naturally arise in the field of [[theoretical computer science]] as a consequence of the widely believed [[P versus NP problem|P ≠ NP]] conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in [[Time complexity|polynomial time]]. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides ''both'' is the classic approximation algorithm of [[Jan Karel Lenstra|Lenstra]], [[David Shmoys|Shmoys]] and [[Éva Tardos|Tardos]]<ref>{{Cite journal|last1=Lenstra|first1=Jan Karel|last2=Shmoys|first2=David B.|last3=Tardos|first3=Éva|date=1990-01-01|title=Approximation algorithms for scheduling unrelated parallel machines|journal=Mathematical Programming|language=en|volume=46|issue=1–3|pages=259–271|doi=10.1007/BF01585745|issn=0025-5610|citeseerx=10.1.1.115.708|s2cid=206799898}}</ref> for [[Scheduling (computing)|scheduling]] on unrelated parallel machines.

The design and [[mathematical analysis|analysis]] of approximation algorithms crucially involves a [[mathematical proof]] certifying the quality of the returned solutions in the worst case.<ref name="Bernard. 2011"/> This distinguishes them from [[heuristic (computer science)|heuristics]] such as [[Simulated annealing|annealing]] or [[genetic algorithm]]s, which find reasonably good solutions on some inputs, but provide no clear indication at the outset on when they may succeed or fail.

There is widespread interest in [[theoretical computer science]] to better understand the limits to which we can approximate certain famous optimization problems. For example, one of the long-standing open questions in computer science is to determine whether there is an algorithm that outperforms the 2-approximation for the Steiner Forest problem by Agrawal et al.<ref>{{Cite book |last1=Agrawal |first1=Ajit |last2=Klein |first2=Philip |last3=Ravi |first3=R. |title=Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 |chapter=When trees collide |date=1991 |chapter-url=http://portal.acm.org/citation.cfm?doid=103418.103437 |language=en |location=New Orleans, Louisiana, United States |publisher=ACM Press |pages=134–144 |doi=10.1145/103418.103437 |isbn=978-0-89791-397-3|s2cid=1245448 }}</ref> The desire to understand hard optimization problems from the perspective of approximability is motivated by the discovery of surprising mathematical connections and broadly applicable techniques to design algorithms for hard optimization problems. One well-known example of the former is the [[Semidefinite programming#Example 3 (Goemans–Williamson max cut approximation algorithm)|Goemans–Williamson algorithm]] for [[maximum cut]], which solves a graph theoretic problem using high dimensional geometry.<ref>{{Cite journal|last1=Goemans|first1=Michel X.|last2=Williamson|first2=David P.|date=November 1995|title=Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming|journal=J. ACM|volume=42|issue=6|pages=1115–1145|doi=10.1145/227683.227684|issn=0004-5411|citeseerx=10.1.1.34.8500|s2cid=15794408}}</ref>