Hardness of approximation

In computer science, hardness of approximation is a field which studies the complexity of approximating optimization problems.

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 than 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.

External links

• Survey, a good starter - by Luca Trevisan