Laura Sanita: On the Simplex method for 0/1 polytopes

Abstract: The Simplex method is one of the most popular algorithms for
solving linear programs, but 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.
In fact, a polynomial pivot rule is not even known for linear programs
over 0/1 polytopes (0/1-LPs), despite the fact that the diameter of a
0/1 polytope is bounded by its dimension.
This talk will focus on the behavior of the Simplex method for 0/1-LPs,
and discuss pivot rules that are guaranteed to require only a
polynomial number of non-degenerate pivots.

Joint work with: Alexander Black, Jesus De Loera, Sean Kafer.

Zoom meeting ID: 654 5562 3260

Zoom link: https://kth-se.zoom.us/j/65455623260