This HTML5 document contains 52 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n17https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Approximation-preserving_reduction
rdf:type
dbo:Software
rdfs:label
Approximation-preserving reduction Redução com Preservação da Aproximação
rdfs:comment
In computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the distance of solutions from optimal is preserved to some degree. Approximation-preserving reductions are a subset of more general reductions in complexity theory; the difference is that approximation-preserving reductions usually make statements on approximation problems or optimization problems, as opposed to decision problems. Em teoria da computabilidade e complexidade computacional, especialmente no estudo de algoritmos de aproximação, uma redução com preservação aproximada é um algoritmo para transformar um problema de otimização em outro problema qualquer, de tal forma que a distância para uma solução ideal é preservada em algum grau. Reduções com preservação aproximada são um subconjunto das mais gerais reduções na teoria da complexidade; a diferença é que a redução com preservação aproximada geralmente criam sentenças sobre a aproximação de problemas ou de problemas de otimização, como oposição aos problemas de decisão.
dcterms:subject
dbc:Reduction_(complexity) dbc:Approximation_algorithms
dbo:wikiPageID
44642859
dbo:wikiPageRevisionID
1096389679
dbo:wikiPageWikiLink
dbr:PTAS_reduction dbr:Poly-APX dbr:Log-APX dbr:Polynomial-time_approximation_scheme dbc:Reduction_(complexity) dbr:Computability_theory dbr:APX dbr:Algorithm dbr:Reduction_(complexity) dbr:L-reduction dbr:Approximation_algorithm dbc:Approximation_algorithms dbr:Computational_problem dbr:Optimization_problem dbr:Decision_problem dbr:Complete_(complexity) dbr:Computational_complexity_theory
owl:sameAs
wikidata:Q25303750 freebase:m.012g45jh dbpedia-pt:Redução_com_Preservação_da_Aproximação n17:2NesT yago-res:Approximation-preserving_reduction
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Mvar dbt:Reflist dbt:Main
dbo:abstract
Em teoria da computabilidade e complexidade computacional, especialmente no estudo de algoritmos de aproximação, uma redução com preservação aproximada é um algoritmo para transformar um problema de otimização em outro problema qualquer, de tal forma que a distância para uma solução ideal é preservada em algum grau. Reduções com preservação aproximada são um subconjunto das mais gerais reduções na teoria da complexidade; a diferença é que a redução com preservação aproximada geralmente criam sentenças sobre a aproximação de problemas ou de problemas de otimização, como oposição aos problemas de decisão. Intuitivamente, um problema A é redutível ao problema B através de uma aproximação, preservando a redução se, dada uma instância de problema A e um (possivelmente aproximado) solucionador para o problema B, pode-se converter a instância de problema A em uma instância do problema B, aplicar o solucionador para o problema B, e recuperar uma solução para o problema A que também tem alguma garantia de aproximação. In computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the distance of solutions from optimal is preserved to some degree. Approximation-preserving reductions are a subset of more general reductions in complexity theory; the difference is that approximation-preserving reductions usually make statements on approximation problems or optimization problems, as opposed to decision problems. Intuitively, problem A is reducible to problem B via an approximation-preserving reduction if, given an instance of problem A and a (possibly approximate) solver for problem B, one can convert the instance of problem A into an instance of problem B, apply the solver for problem B, and recover a solution for problem A that also has some guarantee of approximation.
gold:hypernym
dbr:Algorithm
prov:wasDerivedFrom
wikipedia-en:Approximation-preserving_reduction?oldid=1096389679&ns=0
dbo:wikiPageLength
9454
foaf:isPrimaryTopicOf
wikipedia-en:Approximation-preserving_reduction
Subject Item
dbr:Approximation_algorithm
dbo:wikiPageWikiLink
dbr:Approximation-preserving_reduction
Subject Item
dbr:L-reduction
dbo:wikiPageWikiLink
dbr:Approximation-preserving_reduction
Subject Item
dbr:Gap_reduction
dbo:wikiPageWikiLink
dbr:Approximation-preserving_reduction
Subject Item
dbr:PTAS_reduction
dbo:wikiPageWikiLink
dbr:Approximation-preserving_reduction
Subject Item
dbr:Reduction_(complexity)
dbo:wikiPageWikiLink
dbr:Approximation-preserving_reduction
Subject Item
dbr:APX
dbo:wikiPageWikiLink
dbr:Approximation-preserving_reduction
Subject Item
dbr:Polynomial-time_approximation_scheme
dbo:wikiPageWikiLink
dbr:Approximation-preserving_reduction
Subject Item
dbr:SNP_(complexity)
dbo:wikiPageWikiLink
dbr:Approximation-preserving_reduction
Subject Item
dbr:Facility_location_problem
dbo:wikiPageWikiLink
dbr:Approximation-preserving_reduction
Subject Item
dbr:Exact_algorithm
dbo:wikiPageWikiLink
dbr:Approximation-preserving_reduction
Subject Item
wikipedia-en:Approximation-preserving_reduction
foaf:primaryTopic
dbr:Approximation-preserving_reduction