This HTML5 document contains 77 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Subject Item

dbpedia-es:Conjetura_de_Hirsch

rdfs:label

Conjetura de Hirsch

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

owl:sameAs

n7:02qc4x7

dct:subject

category-es:Epónimos_relacionados_con_las_matemáticas category-es:Conjeturas_matemáticas

foaf:isPrimaryTopicOf

wikipedia-es:Conjetura_de_Hirsch

prop-es:apellido

Kalai

prop-es:authorlink

Francisco Santos Leal Victor Klee Daniel Kleitman Günter M. Ziegler George B. Dantzig Gil Kalai

prop-es:contribution

The Hirsch Conjecture

prop-es:doi

101007 101090 104007

prop-es:fecha

10

prop-es:fechaacceso

11

prop-es:first

George B. Daniel J. Victor Francisco Denis David W. Günter M. Gil

prop-es:id

,

prop-es:issue

1 2

prop-es:journal

Mathematical Programming Annals of Math. Bulletin of the American Mathematical Society Acta Mathematica

prop-es:last

Naddef Dantzig Klee Walkup Kleitman Kalai Santos Ziegler

prop-es:nombre

Gil

prop-es:pages

83 109 383 315 53

prop-es:publisher

Princeton Univ. Press Springer-Verlag

prop-es:ref

harv

prop-es:series

Graduate Texts in Mathematics

prop-es:title

The Hirsch conjecture is true for -polytopes Linear Programming and Extensions Lectures on Polytopes The d-step conjecture for polyhedra of dimension d < 6 A quasi-polynomial bound for the diameter of graphs of polyhedra A counter-example to the Hirsch conjecture

prop-es:url

http://gilkalai.wordpress.com/2010/05/10/francisco-santos-disproves-the-hirsch-conjecture/|título=Francisco Santos Disproves the Hirsch Conjecture

prop-es:volume

26 152 133 176 45

prop-es:year

1989 1994 1992 2012 1963 1967

dbo:wikiPageID

3938668

dbo:wikiPageRevisionID

119639446

dbo:wikiPageExternalLink

n5:Francisco

dbo:wikiPageLength

5106

prov:wasDerivedFrom

n14:0

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.

Subject Item

wikipedia-es:Conjetura_de_Hirsch

foaf:primaryTopic

dbpedia-es:Conjetura_de_Hirsch