Return to search

Combinatorial Polynomial Hirsch Conjecture

The Hirsch Conjecture states that for a d-dimensional polytope with n facets, the diameter of the graph of the polytope is at most n-d. This conjecture was disproven in 2010 by Francisco Santos Leal. However, a polynomial bound in n and d on the diameter of a polytope may still exist. Finding a polynomial bound would provide a worst-case scenario runtime for the Simplex Method of Linear Programming. However working only with polytopes in higher dimensions can prove challenging, so other approaches are welcome. There are many equivalent formulations of the Hirsch Conjecture, one of which is the Combinatorial Polynomial Hirsch Conjecture, which turns the problem into a matter of counting sets.
This thesis explores the Combinatorial Polynomial Hirsch Conjecture.

Identiferoai:union.ndltd.org:CLAREMONT/oai:scholarship.claremont.edu:hmc_theses-1096
Date01 January 2017
CreatorsMiller, Sam
PublisherScholarship @ Claremont
Source SetsClaremont Colleges
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceHMC Senior Theses
Rights© 2017 Sam K Miller, default

Page generated in 0.0016 seconds