| dbo:abstract
|
- In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the polytope must be connected to each other by a path of length at most n − d. The conjecture was first put forth in a letter by to George B. Dantzig in 1957 and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method. The conjecture is now known to be false in general. The Hirsch conjecture was proven for d < 4 and for various special cases, while the best known upper bounds on the diameter are only sub-exponential in n and d. After more than fifty years, a counter-example was announced in May 2010 by Francisco Santos Leal, from the University of Cantabria. The result was presented at the conference 100 Years in Seattle: the mathematics of Klee and Grünbaum and appeared in Annals of Mathematics. Specifically, the paper presented a 43-dimensional polytope of 86 facets with a diameter of more than 43. The counterexample has no direct consequences for the analysis of the simplex method, as it does not rule out the possibility of a larger but still linear or polynomial number of steps. Various equivalent formulations of the problem had been given, such as the d-step conjecture, which states that the diameter of any 2d-facet polytope in d-dimensional Euclidean space is no more than d; Santos Leal's counterexample also disproves this conjecture. (en)
- En optimización y en combinatoria poliédrica, la conjetura de Hirsch afirma que "si un poliedro está definido por n desigualdades lineales en d variables siempre ha de ser posible viajar de cualquier vértice a cualquier otro vértice recorriendo como mucho n-d aristas". En términos un poco más técnicos, afirma que el grafo arista-vértice de un politopo de n-caras en un espacio euclidiano d-dimensional tiene un diámetro no mayor que n − d. Es decir, que cualquiera de dos vértices del politopo deben estar conectados el uno con el otro por una trayectoria de longitud n − d como máximo. La conjetura fue presentada primero en 1957 en una carta de Warren M. Hirsch a George B. Dantzig y es motivada por el análisis del método simplex en programación lineal, a medida que el diámetro de un politopo proporciona un límite más bajo en el número de pasos necesarios por el método simplex. La conjetura de Hirsch fue probada para d < 4 y para varios casos especiales, los límites superiores más conocidos mostraron solamente que los politopos tienen un diámetro sub-exponencial en función de n y d. sin embargo, después de más de cincuenta años, un contraejemplo fue anunciado en mayo de 2010 por Francisco Santos Leal, de la Universidad de Cantabria. el resultado debe ser presentado en la conferencia 100 Years in Seattle: The Mathematics of Klee and Grünbaum. Varias formulaciones equivalentes del problema habían sido dadas, por ejemplo la conjetura d-paso, que indica que el diámetro de cualquier politopo de 2d-caras en un espacio euclidiano d-dimensional no es mayor que d. La conjetura de d-paso era conocida como verdadera para d < 6, pero cuando fue encontrado un contraejemplo el caso general también fue refutado, usando un politopo 43-dimensional de 86 caras con un diámetro de más de 43. El contraejemplo anunciado no tendría ninguna consecuencia directa para el análisis del método simplex, pues no eliminaría la posibilidad de un más grande pero todavía lineal o un número polinómico de pasos. (es)
- 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)
- Гіпотеза Гірша — спростована гіпотеза про діаметр графу багатогранника. (uk)
- Гипотеза Хирша — опровергнутая гипотеза о диаметре графа многогранника. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10536 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Гіпотеза Гірша — спростована гіпотеза про діаметр графу багатогранника. (uk)
- Гипотеза Хирша — опровергнутая гипотеза о диаметре графа многогранника. (ru)
- In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the polytope must be connected to each other by a path of length at most n − d. The conjecture was first put forth in a letter by to George B. Dantzig in 1957 and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method. The conjecture is now known to be false in general. (en)
- En optimización y en combinatoria poliédrica, la conjetura de Hirsch afirma que "si un poliedro está definido por n desigualdades lineales en d variables siempre ha de ser posible viajar de cualquier vértice a cualquier otro vértice recorriendo como mucho n-d aristas". En términos un poco más técnicos, afirma que el grafo arista-vértice de un politopo de n-caras en un espacio euclidiano d-dimensional tiene un diámetro no mayor que n − d. Es decir, que cualquiera de dos vértices del politopo deben estar conectados el uno con el otro por una trayectoria de longitud n − d como máximo. La conjetura fue presentada primero en 1957 en una carta de Warren M. Hirsch a George B. Dantzig y es motivada por el análisis del método simplex en programación lineal, a medida que el diámetro de un politop (es)
- 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
|
- Conjetura de Hirsch (es)
- Hirsch conjecture (en)
- Conjecture de Hirsch (fr)
- Гипотеза Хирша (ru)
- Гіпотеза Гірша (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
