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.
| Identifer | oai:union.ndltd.org:CLAREMONT/oai:scholarship.claremont.edu:hmc_theses-1096 |
| Date | 01 January 2017 |
| Creators | Miller, Sam |
| Publisher | Scholarship @ Claremont |
| Source Sets | Claremont Colleges |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | HMC Senior Theses |
| Rights | © 2017 Sam K Miller, default |
Page generated in 0.0022 seconds