Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Performance of Steepest Descent in 0/1 LPs

Hausdorff Center for Mathematics via YouTube

Overview

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.

Syllabus

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

Taught by

Hausdorff Center for Mathematics

Reviews

Start your review of Performance of Steepest Descent in 0/1 LPs

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.