Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Hardness_of_approximation> ?p ?o. }
Showing items 1 to 15 of
15
with 100 items per page.
- Hardness_of_approximation abstract "In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. It 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.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.".
- Hardness_of_approximation wikiPageExternalLink inapprox.ps.
- Hardness_of_approximation wikiPageExternalLink 05au.
- Hardness_of_approximation wikiPageID "20677277".
- Hardness_of_approximation wikiPageRevisionID "439406158".
- Hardness_of_approximation hasPhotoCollection Hardness_of_approximation.
- Hardness_of_approximation subject Category:Computational_complexity_theory.
- Hardness_of_approximation subject Category:Mathematical_optimization.
- Hardness_of_approximation comment "In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. It complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can be efficiently approximated.".
- Hardness_of_approximation label "Hardness of approximation".
- Hardness_of_approximation sameAs m.0523htj.
- Hardness_of_approximation sameAs Q5656275.
- Hardness_of_approximation sameAs Q5656275.
- Hardness_of_approximation wasDerivedFrom Hardness_of_approximation?oldid=439406158.
- Hardness_of_approximation isPrimaryTopicOf Hardness_of_approximation.