Hardness of approximation
Encyclopedia
In computer science
, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problem
s. It complements the study of approximation algorithm
s 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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problem
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
s. It complements the study of approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
s 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
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
, 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
Unique games conjecture
In computational complexity theory, the Unique Games Conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the value of a certain type of game, known as a unique game, has NP-hard algorithmic complexity...
.
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
PCP (complexity)
In computational complexity theory, a probabilistically checkable proof is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject...
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
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
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.Further reading
- Survey, a good starter - by Luca TrevisanLuca TrevisanLuca Trevisan is a professor of computer science at the University of California, Berkeley. As of winter 2010, he is on leave and an acting professor of computer science at Stanford University....
External links
- CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005, syllabus from the University of WashingtonUniversity of WashingtonUniversity of Washington is a public research university, founded in 1861 in Seattle, Washington, United States. The UW is the largest university in the Northwest and the oldest public university on the West Coast. The university has three campuses, with its largest campus in the University...
, Venkatesan Guruswami and Ryan O'Donnell