In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, hardness of approximation is a field that studies the
algorithmic complexity of finding near-optimal solutions to
optimization problem
In mathematics, engineering, computer science and economics
Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
s.
Scope
Hardness of approximation complements the study of
approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
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
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
, implying that finding a
polynomial time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
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
In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate ''value'' of a certain type of g ...
.
History
Since the early 1970s it was known that many optimization problems could not be solved in polynomial time unless
P = NP
The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
Here, "quickly" means an algorithm exists that ...
, 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
Professor Sartaj Kumar Sahni (born July 22, 1949, in Pune, India) is a computer scientist based in the United States, and is one of the pioneers in the field of data structures. He is a distinguished professor in the Department of Computer and I ...
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
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
. 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.
[.] 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.
Examples
For an example of an NP-hard optimization problem that is hard to approximate, see
set cover
The set cover problem is a classical question in combinatorics, computer science, operations research, and Computational complexity theory, complexity theory.
Given a Set (mathematics), set of elements (henceforth referred to as the Universe ( ...
.
See also
*
PCP theorem
In computational complexity theory, the PCP theorem (also known as the PCP characterization theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs ( proofs that can be checked by a randomiz ...
References
Further reading
*{{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
External links
CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005 syllabus from the
University of Washington
The University of Washington (UW and informally U-Dub or U Dub) is a public research university in Seattle, Washington, United States. Founded in 1861, the University of Washington is one of the oldest universities on the West Coast of the Uni ...
,
Venkatesan Guruswami
Venkatesan Guruswami (born 1976) is a senior scientist at the Simons Institute for the Theory of Computing and Professor of EECS and Mathematics at the University of California, Berkeley. He did his high schooling at Padma Seshadri Bala Bhav ...
and
Ryan O'Donnell
Approximation algorithms
Computational complexity theory
Relaxation (approximation)