| Property |
Value |
| dbo:abstract
|
- 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 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)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
| |
| dbo:wikiPageRevisionID
| |
| prop-es:apellido
| |
| prop-es:authorlink
|
- Günter M. Ziegler (es)
- Victor Klee (es)
- George B. Dantzig (es)
- Daniel Kleitman (es)
- Francisco Santos Leal (es)
- Gil Kalai (es)
- Günter M. Ziegler (es)
- Victor Klee (es)
- George B. Dantzig (es)
- Daniel Kleitman (es)
- Francisco Santos Leal (es)
- Gil Kalai (es)
|
| prop-es:contribution
|
- The Hirsch Conjecture (es)
- The Hirsch Conjecture (es)
|
| prop-es:doi
|
- 101007 (xsd:integer)
- 101090 (xsd:integer)
- 104007 (xsd:integer)
|
| prop-es:fecha
| |
| prop-es:fechaacceso
| |
| prop-es:first
|
- Francisco (es)
- Victor (es)
- Gil (es)
- Denis (es)
- David W. (es)
- George B. (es)
- Daniel J. (es)
- Günter M. (es)
- Francisco (es)
- Victor (es)
- Gil (es)
- Denis (es)
- David W. (es)
- George B. (es)
- Daniel J. (es)
- Günter M. (es)
|
| prop-es:id
| |
| prop-es:issue
|
- 1 (xsd:integer)
- 2 (xsd:integer)
|
| prop-es:journal
|
- Acta Mathematica (es)
- Annals of Math. (es)
- Bulletin of the American Mathematical Society (es)
- Mathematical Programming (es)
- Acta Mathematica (es)
- Annals of Math. (es)
- Bulletin of the American Mathematical Society (es)
- Mathematical Programming (es)
|
| prop-es:last
|
- Santos (es)
- Ziegler (es)
- Dantzig (es)
- Klee (es)
- Kalai (es)
- Kleitman (es)
- Naddef (es)
- Walkup (es)
- Santos (es)
- Ziegler (es)
- Dantzig (es)
- Klee (es)
- Kalai (es)
- Kleitman (es)
- Naddef (es)
- Walkup (es)
|
| prop-es:nombre
| |
| prop-es:pages
|
- 53 (xsd:integer)
- 83 (xsd:integer)
- 109 (xsd:integer)
- 315 (xsd:integer)
- 383 (xsd:integer)
|
| prop-es:publisher
|
- Springer-Verlag (es)
- Princeton Univ. Press (es)
- Springer-Verlag (es)
- Princeton Univ. Press (es)
|
| prop-es:ref
| |
| prop-es:series
|
- Graduate Texts in Mathematics (es)
- Graduate Texts in Mathematics (es)
|
| prop-es:title
|
- The d-step conjecture for polyhedra of dimension d < 6 (es)
- A counter-example to the Hirsch conjecture (es)
- Lectures on Polytopes (es)
- Linear Programming and Extensions (es)
- The Hirsch conjecture is true for -polytopes (es)
- A quasi-polynomial bound for the diameter of graphs of polyhedra (es)
- The d-step conjecture for polyhedra of dimension d < 6 (es)
- A counter-example to the Hirsch conjecture (es)
- Lectures on Polytopes (es)
- Linear Programming and Extensions (es)
- The Hirsch conjecture is true for -polytopes (es)
- A quasi-polynomial bound for the diameter of graphs of polyhedra (es)
|
| prop-es:url
|
- http://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/|título=Francisco Santos Disproves the Hirsch Conjecture (es)
- http://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/|título=Francisco Santos Disproves the Hirsch Conjecture (es)
|
| prop-es:volume
|
- 26 (xsd:integer)
- 45 (xsd:integer)
- 133 (xsd:integer)
- 152 (xsd:integer)
- 176 (xsd:integer)
|
| prop-es:year
|
- 1963 (xsd:integer)
- 1967 (xsd:integer)
- 1989 (xsd:integer)
- 1992 (xsd:integer)
- 1994 (xsd:integer)
- 2012 (xsd:integer)
|
| dct:subject
| |
| rdfs:comment
|
- 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 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)
|
| rdfs:label
|
- Conjetura de Hirsch (es)
- Conjetura de Hirsch (es)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is foaf:primaryTopic
of | |
