February 8, 2024
Title: Adventures in Linear Programming (applied MI talk)
Speaker: Daniel Dadusch
Linear programming, the task of optimizing a linear function over a set of linear inequalities, is one of the most fundamental problems in optimization which connects to many areas of mathematics (combinatorics, high dimensional probability, convex geometry, tropical geometry, …). Despite almost a century of study, many important open problems remain:
Why does the simplex method work well in practice?
Is the diameter of a polyhedron bounded by a polynomial in the dimension and number of inequalities?
Is there a strongly polynomial algorithm for solving linear programs?
In this talk, I will provide the background to these questions, overview progress over the last few decades, including my own contributions.