Performance of Steepest Descent in 0/1 LPs

Explore the performance of steepest descent in 0/1 Linear Programs (LPs) in this 25-minute talk by Sean Kafer at the Hausdorff Center for Mathematics. Delve into the ongoing challenge of finding a polynomial-time pivot rule for the Simplex method, focusing on the special case of 0/1 LPs. Learn about the study of monotone edge-paths generated by following steepest edges, normalized using the 1-norm. Discover how this path can be computed in polynomial time and its strongly-polynomial length. Examine the relationship between steepest descent circuit steps and steepest descent edge steps in 0/1 LPs. Gain insights into a newly devised alternate pivot rule for 0/1 LPs that guarantees following the path generated by steepest edges, requiring only a polynomial number of non-degenerate pivots. Understand the implications of this research, conducted in collaboration with Jesús De Loera, Laura Sanitá, and Alex Black, for the field of combinatorial optimization and the ongoing study of the Simplex method's behavior.

Sean Kafer: Performance of steepest descent in 0/1 LPs