| Property |
Value |
| dbo:abstract
|
- En théorie de la complexité, APX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant. Cette classe est égale à la classe MaxSNP si l'on considère certains types de réductions. Elle contient la classe PTAS, des problèmes qui admettent un schéma d'approximation en temps polynomial. Le problème d'optimisation Vertex Cover appartient par exemple à cette classe (et est complet pour certaines réductions), par contre, le problème de la clique maximum n'appartient pas à cette classe sauf si P = NP. (fr)
- En théorie de la complexité, APX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant. Cette classe est égale à la classe MaxSNP si l'on considère certains types de réductions. Elle contient la classe PTAS, des problèmes qui admettent un schéma d'approximation en temps polynomial. Le problème d'optimisation Vertex Cover appartient par exemple à cette classe (et est complet pour certaines réductions), par contre, le problème de la clique maximum n'appartient pas à cette classe sauf si P = NP. (fr)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 1112 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- En théorie de la complexité, APX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant. Cette classe est égale à la classe MaxSNP si l'on considère certains types de réductions. Elle contient la classe PTAS, des problèmes qui admettent un schéma d'approximation en temps polynomial. Le problème d'optimisation Vertex Cover appartient par exemple à cette classe (et est complet pour certaines réductions), par contre, le problème de la clique maximum n'appartient pas à cette classe sauf si P = NP. (fr)
- En théorie de la complexité, APX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant. Cette classe est égale à la classe MaxSNP si l'on considère certains types de réductions. Elle contient la classe PTAS, des problèmes qui admettent un schéma d'approximation en temps polynomial. Le problème d'optimisation Vertex Cover appartient par exemple à cette classe (et est complet pour certaines réductions), par contre, le problème de la clique maximum n'appartient pas à cette classe sauf si P = NP. (fr)
|
| rdfs:label
|
- APX (Complexitat) (ca)
- APX (complexité) (fr)
- Apx completude (pt)
- Класс APX (ru)
- APX (Complexitat) (ca)
- APX (complexité) (fr)
- Apx completude (pt)
- Класс APX (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:isPartOf
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
