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 .
Attributes | Values |
---|
rdfs:label
| - PTAS reduction (en)
- Redução PTAS (pt)
|
rdfs:comment
| - 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 . (en)
- 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: (pt)
|
dct:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
Link from a Wikipage to an external page
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has abstract
| - 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. (en)
- 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. (pt)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is Wikipage disambiguates
of | |
is foaf:primaryTopic
of | |