| Property |
Value |
| dbo:abstract
|
- Le théorème optimisation/séparation est un théorème d'optimisation combinatoire, un domaine des mathématiques et de l'informatique théorique. C'est une conséquence de la méthode de l'ellipsoïde. Il constitue un résultat majeur en optimisation combinatoire qui fait le lien entre l'approche polyédrique et l'algorithmique. Ce résultat établit l'équivalence, du point de vue de la complexité algorithmique, entre « optimiser » et « séparer », sur un même polyèdre. Un polyèdre convexe P de est constitué par l'ensemble des points satisfaisant un nombre arbitrairement grand mais fini d'inégalités linéaires (i.e. de la forme ).
* Optimiser sur P consiste à déterminer pour toute fonction linéaire .
* Séparer sur P consiste à déterminer, pour tout point , si appartient à P ou non, et sinon, à déterminer un hyperplan séparant de P (i.e. trouver une inégalité linéaire violée par mais satisfaite par tout point de P). On peut optimiser sur un polyèdre en temps polynomial si et seulement si on peut séparer sur ce polyèdre en temps polynomial. (fr)
- Le théorème optimisation/séparation est un théorème d'optimisation combinatoire, un domaine des mathématiques et de l'informatique théorique. C'est une conséquence de la méthode de l'ellipsoïde. Il constitue un résultat majeur en optimisation combinatoire qui fait le lien entre l'approche polyédrique et l'algorithmique. Ce résultat établit l'équivalence, du point de vue de la complexité algorithmique, entre « optimiser » et « séparer », sur un même polyèdre. Un polyèdre convexe P de est constitué par l'ensemble des points satisfaisant un nombre arbitrairement grand mais fini d'inégalités linéaires (i.e. de la forme ).
* Optimiser sur P consiste à déterminer pour toute fonction linéaire .
* Séparer sur P consiste à déterminer, pour tout point , si appartient à P ou non, et sinon, à déterminer un hyperplan séparant de P (i.e. trouver une inégalité linéaire violée par mais satisfaite par tout point de P). On peut optimiser sur un polyèdre en temps polynomial si et seulement si on peut séparer sur ce polyèdre en temps polynomial. (fr)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 1956 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
| |
| prop-fr:auteur
| |
| prop-fr:journal
| |
| prop-fr:lang
| |
| prop-fr:pages
| |
| prop-fr:titre
|
- The ellipsoid method and its consequences in combinatorial optimization (fr)
- The ellipsoid method and its consequences in combinatorial optimization (fr)
|
| prop-fr:volume
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- Le théorème optimisation/séparation est un théorème d'optimisation combinatoire, un domaine des mathématiques et de l'informatique théorique. C'est une conséquence de la méthode de l'ellipsoïde. Il constitue un résultat majeur en optimisation combinatoire qui fait le lien entre l'approche polyédrique et l'algorithmique. Ce résultat établit l'équivalence, du point de vue de la complexité algorithmique, entre « optimiser » et « séparer », sur un même polyèdre. On peut optimiser sur un polyèdre en temps polynomial si et seulement si on peut séparer sur ce polyèdre en temps polynomial. (fr)
- Le théorème optimisation/séparation est un théorème d'optimisation combinatoire, un domaine des mathématiques et de l'informatique théorique. C'est une conséquence de la méthode de l'ellipsoïde. Il constitue un résultat majeur en optimisation combinatoire qui fait le lien entre l'approche polyédrique et l'algorithmique. Ce résultat établit l'équivalence, du point de vue de la complexité algorithmique, entre « optimiser » et « séparer », sur un même polyèdre. On peut optimiser sur un polyèdre en temps polynomial si et seulement si on peut séparer sur ce polyèdre en temps polynomial. (fr)
|
| rdfs:label
|
- Théorème optimisation/séparation (fr)
- Théorème optimisation/séparation (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
