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 NP=P, but in many of these problems the optimal solution could be efficiently approximated to a certain degree. In the early 1990s, with the development of PCP theory, it became clear that there is a limit to the approximability of many of these optimization problems: for many optimization problems there is a threshold beyond which they are NP-hard to approximate. 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.
- CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005, syllabus from the University of Washington, Venkatesan Guruswami and Ryan O'Donnell
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|