| dbo: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)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3360 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| 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)
|
| rdfs:label
|
- PTAS reduction (en)
- Redução PTAS (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
