Hardness of approximation

Hardness of approximation complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can be efficiently approximated. Typically such limits show a factor of approximation beyond which a problem becomes NP-hard, implying that finding a polynomial time approximation for the problem is impossible unless NP=P. Some hardness of approximation results, however, are based on other hypotheses, a notable one among which is the unique games conjecture.

Since the early 1970s it was known that many optimization problems could not be solved in polynomial time unless P = NP, but in many of these problems the optimal solution could be efficiently approximated to a certain degree. In the 1970s, Teofilo F. Gonzalez and Sartaj Sahni began the study of hardness of approximation, by showing that certain optimization problems were NP-hard even to approximate to within a given approximation ratio. That is, for these problems, there is a threshold such that any polynomial-time approximation with approximation ratio beyond this threshold could be used to solve NP-complete problems in polynomial time.{{citation

| last1 = Sahni | first1 = Sartaj | author1-link = Sartaj Sahni

| last2 = Gonzalez | first2 = Teofilo

| issue = 3

| journal = Journal of the ACM

| mr = 0408313

| pages = 555–565

| title = P-complete approximation problems

| volume = 23

| year = 1976 | doi=10.1145/321958.321975| hdl = 10338.dmlcz/103883

| hdl-access = free

}}. In the early 1990s, with the development of PCP theory, it became clear that many more approximation problems were hard to approximate, and that (unless P = NP) many known approximation algorithms achieved the best possible approximation ratio.

Hardness of approximation theory deals with studying the approximation threshold of such problems.

For an example of an NP-hard optimization problem that is hard to approximate, see set cover.

• PCP theorem

{{reflist}}

• {{citation|url=http://cs.stanford.edu/people/trevisan/pubs/inapprox.pdf|first=Luca|last=Trevisan|authorlink=Luca Trevisan|title=Inapproximability of Combinatorial Optimization Problems|date=July 27, 2004|arxiv=cs/0409043 |bibcode=2004cs........9043T }}

• [http://www.cs.washington.edu/education/courses/533/05au/ CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005], syllabus from the University of Washington, Venkatesan Guruswami and Ryan O'Donnell

Category:Approximation algorithms

Category:Computational complexity theory

Category:Relaxation (approximation)