Events by date

Title: Generating Short Monotone Paths in 0/1 LPs: From Circuits to Simplex

Speaker: Sean Kafer Affiliation: University of Waterloo Zoom: 945 0789 9910 (passcode: kafer)

Abstract: 

Even after decades of study, it is unknown whether there exists a pivot rule for the Simplex method that always solves an LP with only a polynomial number of pivots.  This remains unknown even in the special case of 0/1 LPs - i.e., LPs defined over 0/1 polytopes - a case that includes many extensively studied problems in combinatorial optimization.