Hardness of approximation

In computer science, hardness of approximation is a field that studies the complexity of finding near-optimal solutions to optimization problems. It complements the study of approximation algorithms by proving that for certain classes of problems, there are no efficient algorithms that would be guaranteed to find solutions that are within a small approximation factor of the optimal solution.

Since the early 1970's 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 1990's, 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.

Examples

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

See also

• PCP theorem

Further reading

• Survey, a good starter - by Luca Trevisan

External links

• CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005, syllabus from the University of Washington, Venkatesan Guruswami and Ryan O'Donnell