Return to Colloquia & Seminar listing
PhD Exit Seminar: Combinatorial Problems Motivated by the Simplex Method
Special Events| Speaker: | Zhenyang Zhang, UC Davis |
| Location: | 3106 MSB |
| Start time: | Thu, Jun 9 2022, 12:00PM |
Title: Combinatorial Problems Motivated by the Simplex Method
Abstract: The simplex method is one of the most important algorithms for solving linear programs. Yet it is still not known whether there is a pivot rule that reaches optimum in polynomial number of steps. In fact, whether the diameter of the 1-skeleton of polytopes is bounded by a polynomial in dimension and number of constraints is still open (Polynomial Hirsch Conjecture). This talk focuses on two different topics: the counting problems on directed polytope graphs, and diameter of cocircuit graphs of oriented matroids, and discusses how they are related to Polynomial Hirsch Conjecture and the simplex method.