Abstract:
Polytopes are ubiquitous in optimization, since many optimization problems may be formulated as finding the furthest point in some direction on a polytope. Such a problem is called a linear program, and one of the most famous ways to solve a linear program is to use the simplex method. Geometrically, solving a linear program with the simplex method corresponds to following a path on the graph of a polytope (i.e., its set of vertices and edges). A key challenge in studying the simplex method is that there are many possible ways to choose a path called pivot rules, and it is a fundamental open problem to prove whether there exists a pivot rule for the simplex method that guarantees a polynomial run-time. Motivated by this problem, in this talk I will introduce a taxonomy of pivot rules and show how this taxonomy gives rise to a polyhedral construction called the pivot rule polytope. Then I will discuss how polytopes in algebraic combinatorics such as permutohedra, associahedra, and multiplihedra arise as pivot rule polytopes. This talk is based on joint work with Jesús De Loera, Niklas Lutjeharms, and Raman Sanyal.
Note: This talk begins with a pre-seminar (aimed at graduate students) at 3:30–4:00. The main talk starts at 4:10.
Join Zoom Meeting: https://washington.zoom.us/j/
Meeting ID: 915 4733 5974