Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Hirsch_conjecture> ?p ?o. }
Showing items 1 to 29 of
29
with 100 items per page.
- Hirsch_conjecture abstract "In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the generally false 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 Warren M. Hirsch 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 Hirsch conjecture was proven for d < 4 and for various special cases. The best known upper bounds showed only that polytopes have sub-exponential diameter as a function of n and d. After more than fifty years, a counter-example was announced in May 2010 by Francisco Santos, 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.".
- Hirsch_conjecture wikiPageExternalLink 2012-12-86.pdf.
- Hirsch_conjecture wikiPageID "10412371".
- Hirsch_conjecture wikiPageRevisionID "567741215".
- Hirsch_conjecture hasPhotoCollection Hirsch_conjecture.
- Hirsch_conjecture subject Category:Conjectures.
- Hirsch_conjecture subject Category:Disproved_conjectures.
- Hirsch_conjecture subject Category:Polyhedral_combinatorics.
- Hirsch_conjecture type Abstraction100002137.
- Hirsch_conjecture type Cognition100023271.
- Hirsch_conjecture type Concept105835747.
- Hirsch_conjecture type Conjectures.
- Hirsch_conjecture type Content105809192.
- Hirsch_conjecture type Hypothesis105888929.
- Hirsch_conjecture type Idea105833840.
- Hirsch_conjecture type PsychologicalFeature100023100.
- Hirsch_conjecture type Speculation105891783.
- Hirsch_conjecture comment "In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the generally false 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 Warren M. Hirsch to George B.".
- Hirsch_conjecture label "Conjecture de Hirsch".
- Hirsch_conjecture label "Conjetura de Hirsch".
- Hirsch_conjecture label "Hirsch conjecture".
- Hirsch_conjecture sameAs Conjetura_de_Hirsch.
- Hirsch_conjecture sameAs Conjecture_de_Hirsch.
- Hirsch_conjecture sameAs m.02qc4x7.
- Hirsch_conjecture sameAs Q2993326.
- Hirsch_conjecture sameAs Q2993326.
- Hirsch_conjecture sameAs Hirsch_conjecture.
- Hirsch_conjecture wasDerivedFrom Hirsch_conjecture?oldid=567741215.
- Hirsch_conjecture isPrimaryTopicOf Hirsch_conjecture.