From linear programming to particle collisions

Prof. Dr. Raman Sanyal (MPI für Mathematik in den Naturwissenschaften, Leipzig):
From linear programming to particle collisions

ABSTRACT: Linear programming (or linear optimization) seeks to maximize a linear function over a subset of real space defined by a finite number of linear inequalities. A widely used method to solve linear programs is the simplex algorithm, which iteratively moves from one feasible solution to another until an optimal solution is found. A crucial component of this method is the pivot rule, which determines the sequence of solutions visited. The holy grail in linear optimization is finding a pivot rule that is universally efficient across all problem instances.

To study the behavior of families of pivot rules on a given linear program, we defined a geometric structure called the pivot rule polytope. Although pivot rule polytopes have not got us closer to the holy grail yet, they have uncovered surprising connections to other areas of mathematics.  In this talk, I will present two such connections. The first is link between toric varieties in Grassmannian and flag varieties, which are governed by matroids and flag matroids, respectively. The second, on which I will focus, shows how the geometry of pivot rule spaces describes the combinatorics of collisions of particles constrained to lines in the plane. No expert knowledge is required for the talk.  This work is based on joint research with Alex Black, Jesús A. De Loera, and Niklas Lütjeharms.

Zur Ankündigungpdf, 219 kb