PTAS reduction
http://dbpedia.org/resource/PTAS_reduction
In computational complexity theory, a PTAS reduction is an approximation-preserving reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approximation scheme (PTAS) and is used to define completeness for certain classes of optimization problems such as APX. Notationally, if there is a PTAS reduction from a problem A to a problem B, we write .
rdf:langString
Na teoria de complexidade computacional, uma redução PTAS é uma que é geralmente usada para fazer reduções junto à soluções para . Isso preserva a propriedade que um problema possui um esquema de aproximação em tempo polinomial (PTAS) e é usado para definir completude para certas classes de otimização de problemas como APX. Por definição, se existe uma redução PTAS de um problema A para um problema B, nós escrevemos . Formalmente, definimos a redução PTAS de A para B usando três funções computáveis em tempo polinomial, f, g, e α, com a seguintes propriedades:
rdf:langString
rdf:langString
PTAS reduction
rdf:langString
Redução PTAS
xsd:integer
9010084
xsd:integer
1102026234
rdf:langString
In computational complexity theory, a PTAS reduction is an approximation-preserving reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approximation scheme (PTAS) and is used to define completeness for certain classes of optimization problems such as APX. Notationally, if there is a PTAS reduction from a problem A to a problem B, we write . With ordinary polynomial-time many-one reductions, if we can describe a reduction from a problem A to a problem B, then any polynomial-time solution for B can be composed with that reduction to obtain a polynomial-time solution for the problem A. Similarly, our goal in defining PTAS reductions is so that given a PTAS reduction from an optimization problem A to a problem B, a PTAS for B can be composed with the reduction to obtain a PTAS for the problem A.
rdf:langString
Na teoria de complexidade computacional, uma redução PTAS é uma que é geralmente usada para fazer reduções junto à soluções para . Isso preserva a propriedade que um problema possui um esquema de aproximação em tempo polinomial (PTAS) e é usado para definir completude para certas classes de otimização de problemas como APX. Por definição, se existe uma redução PTAS de um problema A para um problema B, nós escrevemos . Com redução em tempo polinomial, se pudermos descrever a redução de um problema A para um problema B, então qualquer solução em tempo polinomial para B pode ser composta com a redução para obter uma solução em tempo polinomial para o problema A. Similarmente, nosso objetivo em definir as reduções PTAS é que para uma dada redução PTAS de um problema de otimização A para um problema B, um PTAS para B pode ser composto com uma redução para obter um PTAS para um problema A. Formalmente, definimos a redução PTAS de A para B usando três funções computáveis em tempo polinomial, f, g, e α, com a seguintes propriedades:
* f mapeia instâncias do problema A para instâncias do problema B.
* g pega uma instância x de um problema A, uma solução aproximada para o seguinte problema em B, e um parâmetro de erro ε e produz uma solução aproximada para x.
* α mapeia parâmetros de erro de soluções para instâncias do problema em A para parâmetros de erro de soluções para o problema em B.
* Se a solução y para (uma instância do problema B) for pelo menos vezes pior que a solução ótima, então a solução que leva para x (uma instância do problema A) é pelo menos vezes pior que a solução ótima.
xsd:nonNegativeInteger
3360