Prof. Raman Sanyal
Mo., 19.6.2023, 18:00
Arnimallee 3, Hörsaal 001

Titel: From linear programming to colliding particles

Abstract:
The simplex algorithm is the method of choice for solving linear optimization
problems in practice. However, it is a famous open problem to show that
the simplex algorithm also performs well in theory. From a discrete-geometric
perspective, the simplex algorithm follows a path in the graph of a
convex polytope and the path is determined by a so-called pivot rule. The
challenge is to find a pivot rule that always takes a “short” path.

In recent work, we defined and studied a type of pivot rules that, for any given 
instance of a linear optimization problem, yields a (polyhedral) space  
of pivot rules. While this has not (yet!) solved the running time problem, these 
spaces of pivot rules have provided us with new connections and perspectives 
to objects from completely different areas of math. In this talk I will explain how 
spaces of pivot rules on nearly-trivial linear programming instances give a new 
perspective on the not-so-trivial behavior of particles on lines on planes… 
All we will need is some linear algebra in the plane and combinatorics.