| dbo:abstract |
In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. (en) В информатике сложность аппроксимации — это область изучения вычислительной сложности поиска решений задач оптимизации, близких к оптимальным. (ru) В інформатиці складність апроксимації — це галузь вивчення обчислювальної складності пошуку розв'язків задач оптимізації, близьких до оптимальних. (uk) |
| dbo:wikiPageExternalLink |
http://cs.stanford.edu/people/trevisan/pubs/inapprox.pdf%7Cfirst=Luca%7Clast=Trevisan%7Cauthorlink=Luca http://www.cs.washington.edu/education/courses/533/05au/ |
| dbo:wikiPageID |
20677277 (xsd:integer) |
| dbo:wikiPageLength |
2936 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1077535213 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Sartaj_Sahni dbr:Approximation_algorithm dbr:University_of_Washington dbc:Approximation_algorithms dbr:NP-hard dbc:Relaxation_(approximation) dbr:Computational_complexity_theory dbr:Computer_science dbr:PCP_theorem dbr:Teofilo_F._Gonzalez dbc:Computational_complexity_theory dbr:Polynomial_time dbr:Approximation_ratio dbr:Optimization_problem dbr:Unique_games_conjecture dbr:Venkatesan_Guruswami dbr:PCP_(complexity) dbr:P_=_NP dbr:Set_cover dbr:NP=P |
| dbp:wikiPageUsesTemplate |
dbt:Citation dbt:Reflist |
| dct:subject |
dbc:Approximation_algorithms dbc:Relaxation_(approximation) dbc:Computational_complexity_theory |
| gold:hypernym |
dbr:Field |
| rdfs:comment |
In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. (en) В информатике сложность аппроксимации — это область изучения вычислительной сложности поиска решений задач оптимизации, близких к оптимальным. (ru) В інформатиці складність апроксимації — це галузь вивчення обчислювальної складності пошуку розв'язків задач оптимізації, близьких до оптимальних. (uk) |
| rdfs:label |
Hardness of approximation (en) Сложность аппроксимации (ru) Складність апроксимації (uk) |
| owl:sameAs |
freebase:Hardness of approximation yago-res:Hardness of approximation wikidata:Hardness of approximation dbpedia-ru:Hardness of approximation dbpedia-uk:Hardness of approximation https://global.dbpedia.org/id/4kx82 |
| prov:wasDerivedFrom |
wikipedia-en:Hardness_of_approximation?oldid=1077535213&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Hardness_of_approximation |
| is dbo:knownFor of |
dbr:Teofilo_F._Gonzalez dbr:Chris_Umans |
| is dbo:wikiPageRedirects of |
dbr:Hard_to_approximate dbr:Inapproximability |
| is dbo:wikiPageWikiLink of |
dbr:Carsten_Lund dbr:Approximation_algorithm dbr:Interactive_proof_system dbr:List_of_numerical_analysis_topics dbr:Analysis_of_Boolean_functions dbr:Oded_Regev_(computer_scientist) dbr:Partial_word dbr:Clique_problem dbr:Graph_bandwidth dbr:Shuchi_Chawla dbr:Clique_(graph_theory) dbr:Clique_cover dbr:Computational_problem dbr:Ideal_lattice dbr:PCP_theorem dbr:Probabilistically_checkable_proof dbr:Maximum_common_induced_subgraph dbr:Gadget_(computer_science) dbr:Irit_Dinur dbr:Janka_Chlebíková dbr:K-minimum_spanning_tree dbr:Uriel_Feige dbr:Reduction_(complexity) dbr:Teofilo_F._Gonzalez dbr:Tetris dbr:Johan_Håstad dbr:Bipartite_dimension dbr:Sanjeev_Khanna dbr:Mihalis_Yannakakis dbr:Rajeev_Motwani dbr:Chris_Umans dbr:Long_code_(mathematics) dbr:Mahjong_solitaire dbr:Unique_games_conjecture dbr:Hard_to_approximate dbr:Inapproximability |
| is dbp:knownFor of |
dbr:Chris_Umans |
| is foaf:primaryTopic of |
wikipedia-en:Hardness_of_approximation |