The Simplex method is one of the most popular algorithms to solve linear programs (LPs).
Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to an adjacent extreme point solution along an improving edge-direction of the underlying polyhedron. Despite decades of study, it is still not known whether there exists a pivot rule that guarantees it will always reach an optimal solution with a polynomial number of steps.
This talk will focus on recent developments and results regarding the analysis of the Simplex algorithm's performance.