| Property |
Value |
| dbo:abstract
|
- En mathématiques, et plus précisément en théorie de l'optimisation et en théorie des graphes, la conjecture de Hirsch affirme que le graphe des sommets et des arêtes d'un polytope de dimension d ayant n faces (de dimension d-1) a un diamètre ne dépassant pas n − d, c'est-à-dire que deux sommets du polytope peuvent toujours être reliés par un chemin formé d'au plus n − d arêtes. Cette conjecture apparut dans une lettre écrite par Warren M. Hirsch à George Dantzig en 1957 ; elle était motivée parl'analyse de l'algorithme du simplexe (en programmation linéaire), car le diamètre d'un polytope est une borne inférieure du nombre d'étapes demandées par cet algorithme. La conjecture de Hirsch fut démontrée pour d < 4 et pour de nombreux autres cas particuliers. Cependant, les meilleures bornes supérieures connues montraient seulement que le diamètre des polytopes était une fonction sous-exponentielle de n et d. Après plus de cinquante ans, un contre-exemple fut annoncé en mai 2010 par Francisco Santos (de l'université de Cantabrie). Ce résultat fut présenté lors de la conférence 100 Years in Seattle : the mathematics of Klee and Grünbaum. De nombreuses formes équivalentes de la conjecture étaient connues, comme la conjecture des d étapes, qui affirme que le diamètre d'un polytope de dimension d, ayant 2d faces, est au plus d ; cette conjecture était démontrée pour d < 6. Là encore, un contre-exemple est à présent connu en dimension 43 (un polytope à 86 faces de diamètre > 43). Ces contre-exemples n'ont cependant pas d'incidence directe sur l'analyse de l'algorithme du simplexe, le nombre d'étapes de ce dernier pouvant rester linéaire, ou du moins polynomial. Santos a reçu le prix Fulkerson en 2015 pour son contre-exemple. (fr)
- En mathématiques, et plus précisément en théorie de l'optimisation et en théorie des graphes, la conjecture de Hirsch affirme que le graphe des sommets et des arêtes d'un polytope de dimension d ayant n faces (de dimension d-1) a un diamètre ne dépassant pas n − d, c'est-à-dire que deux sommets du polytope peuvent toujours être reliés par un chemin formé d'au plus n − d arêtes. Cette conjecture apparut dans une lettre écrite par Warren M. Hirsch à George Dantzig en 1957 ; elle était motivée parl'analyse de l'algorithme du simplexe (en programmation linéaire), car le diamètre d'un polytope est une borne inférieure du nombre d'étapes demandées par cet algorithme. La conjecture de Hirsch fut démontrée pour d < 4 et pour de nombreux autres cas particuliers. Cependant, les meilleures bornes supérieures connues montraient seulement que le diamètre des polytopes était une fonction sous-exponentielle de n et d. Après plus de cinquante ans, un contre-exemple fut annoncé en mai 2010 par Francisco Santos (de l'université de Cantabrie). Ce résultat fut présenté lors de la conférence 100 Years in Seattle : the mathematics of Klee and Grünbaum. De nombreuses formes équivalentes de la conjecture étaient connues, comme la conjecture des d étapes, qui affirme que le diamètre d'un polytope de dimension d, ayant 2d faces, est au plus d ; cette conjecture était démontrée pour d < 6. Là encore, un contre-exemple est à présent connu en dimension 43 (un polytope à 86 faces de diamètre > 43). Ces contre-exemples n'ont cependant pas d'incidence directe sur l'analyse de l'algorithme du simplexe, le nombre d'étapes de ce dernier pouvant rester linéaire, ou du moins polynomial. Santos a reçu le prix Fulkerson en 2015 pour son contre-exemple. (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 5098 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1967 (xsd:integer)
- 1989 (xsd:integer)
- 1992 (xsd:integer)
- 1994 (xsd:integer)
- 1998 (xsd:integer)
- 2012 (xsd:integer)
|
| prop-fr:annéePremièreÉdition
| |
| prop-fr:auteur
| |
| prop-fr:collection
| |
| prop-fr:date
| |
| prop-fr:doi
|
- 10.100700 (xsd:double)
- 10.109000 (xsd:double)
- 10.400700 (xsd:double)
|
| prop-fr:id
|
- Kalai 2010 (fr)
- Kalai et Kleitman 1992 (fr)
- Kalai 2010 (fr)
- Kalai et Kleitman 1992 (fr)
|
| prop-fr:isbn
| |
| prop-fr:journal
|
- Mathematical Programming (fr)
- Mathematical Programming (fr)
|
| prop-fr:langue
| |
| prop-fr:lienAuteur
|
- Günter M. Ziegler (fr)
- Günter M. Ziegler (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:mathReviews
|
- 206823 (xsd:integer)
- 1017214 (xsd:integer)
|
| prop-fr:nom
| |
| prop-fr:numéro
|
- 1 (xsd:integer)
- 2 (xsd:integer)
|
| prop-fr:numéroD'édition
| |
| prop-fr:numéroDansCollection
| |
| prop-fr:pages
|
- 53 (xsd:integer)
- 109 (xsd:integer)
- 315 (xsd:integer)
- 383 (xsd:integer)
|
| prop-fr:pagesTotales
| |
| prop-fr:passage
| |
| prop-fr:prénom
|
- Denis (fr)
- Victor (fr)
- David W. (fr)
- Gil (fr)
- Francisco (fr)
- Günter M. (fr)
- Denis (fr)
- Victor (fr)
- David W. (fr)
- Gil (fr)
- Francisco (fr)
- Günter M. (fr)
|
| prop-fr:périodique
| |
| prop-fr:titre
|
- The d-step conjecture for polyhedra of dimension d < 6 (fr)
- A counterexample to the Hirsch conjecture (fr)
- Lectures on Polytopes (fr)
- Linear Programming and Extensions (fr)
- The Hirsch conjecture is true for -polytopes (fr)
- A quasi-polynomial bound for the diameter of graphs of polyhedra (fr)
- The d-step conjecture for polyhedra of dimension d < 6 (fr)
- A counterexample to the Hirsch conjecture (fr)
- Lectures on Polytopes (fr)
- Linear Programming and Extensions (fr)
- The Hirsch conjecture is true for -polytopes (fr)
- A quasi-polynomial bound for the diameter of graphs of polyhedra (fr)
|
| prop-fr:titreChapitre
|
- The Hirsch Conjecture (fr)
- The Hirsch Conjecture (fr)
|
| prop-fr:url
|
- http://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/|site=gilkalai.wordpress.com|titre=Francisco Santos Disproves the Hirsch Conjecture (fr)
- http://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/|site=gilkalai.wordpress.com|titre=Francisco Santos Disproves the Hirsch Conjecture (fr)
|
| prop-fr:volume
|
- 26 (xsd:integer)
- 45 (xsd:integer)
- 133 (xsd:integer)
- 176 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| dct:subject
| |
| rdfs:comment
|
- En mathématiques, et plus précisément en théorie de l'optimisation et en théorie des graphes, la conjecture de Hirsch affirme que le graphe des sommets et des arêtes d'un polytope de dimension d ayant n faces (de dimension d-1) a un diamètre ne dépassant pas n − d, c'est-à-dire que deux sommets du polytope peuvent toujours être reliés par un chemin formé d'au plus n − d arêtes. Cette conjecture apparut dans une lettre écrite par Warren M. Hirsch à George Dantzig en 1957 ; elle était motivée parl'analyse de l'algorithme du simplexe (en programmation linéaire), car le diamètre d'un polytope est une borne inférieure du nombre d'étapes demandées par cet algorithme. (fr)
- En mathématiques, et plus précisément en théorie de l'optimisation et en théorie des graphes, la conjecture de Hirsch affirme que le graphe des sommets et des arêtes d'un polytope de dimension d ayant n faces (de dimension d-1) a un diamètre ne dépassant pas n − d, c'est-à-dire que deux sommets du polytope peuvent toujours être reliés par un chemin formé d'au plus n − d arêtes. Cette conjecture apparut dans une lettre écrite par Warren M. Hirsch à George Dantzig en 1957 ; elle était motivée parl'analyse de l'algorithme du simplexe (en programmation linéaire), car le diamètre d'un polytope est une borne inférieure du nombre d'étapes demandées par cet algorithme. (fr)
|
| rdfs:label
|
- Conjecture de Hirsch (fr)
- Conjetura de Hirsch (es)
- Hirsch conjecture (en)
- Гипотеза Хирша (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
