| dbo:abstract
|
- 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. (en)
- 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. (pt)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9454 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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. (en)
- 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. (pt)
|
| rdfs:label
|
- Approximation-preserving reduction (en)
- Redução com Preservação da Aproximação (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
