Probabilistic Analysis of the Simpler Method and Polytope Diameter

Explore a comprehensive lecture on the probabilistic analysis of the simplex method and polytope diameter. Delve into the progress made in understanding the shadow vertex simplex method across three settings: smoothed polytopes, well-conditioned polytopes, and random polytopes with constraints drawn uniformly from the sphere. Examine improvements and simplifications in the complexity analysis of solving smoothed linear programs, and investigate the challenging question of polytope diameter. Learn how randomly chosen shadow paths yield the best known diameter bounds for well-conditioned polytopes and nearly tight diameter bounds for random spherical polytopes. Discover open problems in the field, including quantifying the effectiveness of the simplex method in re-optimizing after adding constraints and exploring the potential of smoothed analysis to explain low iteration counts in interior point methods for solving linear programs.

Introduction
Simplex method
Shadow vertex rule
Why use simplex
Shadow vertex method
Smooth analysis
WhyLinear programming
Results
Key quantity
Shadow bounds
Solution
Questions
Polyhedral duality
Bounds
Perimeter
Polytope diameter
Wide polyhedra
Shadow vertex
Shadow simplex paths
Asymptotic diameter
Summary