Editing Approximation algorithm (section)

== Hardness of approximation ==
Approximation algorithms as a research area is closely related to and informed by [[Hardness of approximation|inapproximability theory]] where the non-existence of efficient algorithms with certain approximation ratios is proved (conditioned on widely believed hypotheses such as the P ≠ NP conjecture) by means of [[Reduction (complexity)|reductions]]. In the case of the metric traveling salesman problem, the best known inapproximability result rules out algorithms with an approximation ratio less than 123/122 ≈ 1.008196 unless P = NP, Karpinski, Lampis, Schmied.<ref>{{Cite journal|last1=Karpinski|first1=Marek|last2=Lampis|first2=Michael|last3=Schmied|first3=Richard|date=2015-12-01|title=New inapproximability bounds for TSP|journal=Journal of Computer and System Sciences|volume=81|issue=8|pages=1665–1677|doi=10.1016/j.jcss.2015.06.003|arxiv=1303.6437}}</ref> Coupled with the knowledge of the existence of Christofides' 1.5 approximation algorithm, this tells us that the threshold of approximability for metric traveling salesman (if it exists) is somewhere between 123/122 and 1.5.

While inapproximability results have been proved since the 1970s, such results were obtained by ad hoc means and no systematic understanding was available at the time. It is only since the 1990 result of Feige, Goldwasser, Lovász, Safra and Szegedy on the inapproximability of [[Independent set (graph theory)|Independent Set]]<ref>{{Cite journal|last1=Feige|first1=Uriel|last2=Goldwasser|first2=Shafi|last3=Lovász|first3=Laszlo|last4=Safra|first4=Shmuel|last5=Szegedy|first5=Mario|date=March 1996|title=Interactive Proofs and the Hardness of Approximating Cliques|journal=J. ACM|volume=43|issue=2|pages=268–292|doi=10.1145/226643.226652|issn=0004-5411|doi-access=free}}</ref> and the famous [[PCP theorem]],<ref>{{Cite journal|last1=Arora|first1=Sanjeev|last2=Safra|first2=Shmuel|date=January 1998|title=Probabilistic Checking of Proofs: A New Characterization of NP|journal=J. ACM|volume=45|issue=1|pages=70–122|doi=10.1145/273865.273901|s2cid=751563|issn=0004-5411|doi-access=free}}</ref> that modern tools for proving inapproximability results were uncovered. The PCP theorem, for example, shows that [[David S. Johnson|Johnson's]] 1974 approximation algorithms for [[Maximum satisfiability problem|Max SAT]], [[Set cover problem|set cover]], [[Independent set (graph theory)|independent set]] and [[Graph coloring|coloring]] all achieve the optimal approximation ratio, assuming P ≠ NP.<ref>{{Cite journal|last=Johnson|first=David S.|date=1974-12-01|title=Approximation algorithms for combinatorial problems|journal=Journal of Computer and System Sciences|volume=9|issue=3|pages=256–278|doi=10.1016/S0022-0000(74)80044-9|doi-access=free}}</ref>