Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Linear programming is a core problem in optimization, and geometrically, it is the problem of finding the highest point in some direction on a polytope. The standard combinatorial algorithm for solving linear programs is the simplex method, which works by walking from vertex to vertex of the polytope along edges moving higher at each step. We call such a walk a monotone path. There are many ways for the simplex method to choose monotone paths called pivot rules, and the main open problem in the area is to find a pivot rule that guarantees the path followed is always of polynomial length. In this talk, I will discuss an approach to this problem grounded in understanding the space of monotone paths on a polytope and pivot rules for a fixed linear program combinatorially. My focus will be on examples of these spaces.

5:45pm Celebratory refreshments