In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, hardness of approximation is a field that studies the
algorithmic complexity
Algorithmic may refer to:
*Algorithm, step-by-step instructions for a calculation
**Algorithmic art, art made by an algorithm
**Algorithmic composition, music made by an algorithm
** Algorithmic trading, trading decisions made by an algorithm
**Alg ...
of finding near-optimal solutions to
optimization problem
In mathematics, computer science and economics, 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 ...
s.
Scope
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
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 ga ...
.
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. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used above ...
, 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
An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...
. 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 complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the un ...
.
See also
*
PCP theorem
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
External links
CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005 syllabus from the
University of Washington
The University of Washington (UW, simply Washington, or informally U-Dub) is a public research university in Seattle, Washington.
Founded in 1861, Washington is one of the oldest universities on the West Coast; it was established in Seattl ...
,
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 Bhavan ...
and Ryan O'Donnell
Approximation algorithms
Computational complexity theory
Relaxation (approximation)