BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Sean Kafer (remote) (Georgia Tech) DTSTART:20250424T210000Z DTEND:20250424T220000Z DTSTAMP:20260513T201751Z UID:SFUOR/54 DESCRIPTION:Title: S olving 0/1 Linear Programs in Strongly Polynomial Time with Simplex\nb y Sean Kafer (remote) (Georgia Tech) as part of PIMS-CORDS SFU Operations Research Seminar\n\nLecture held in ASB 10908.\n\nAbstract\nThe Simplex me thod for solving linear programs (LPs) is one of the most widely used LP s olvers due to\nthe fact that it runs very quickly in practice. However\, d espite its practical efficiency and decades of study\, it remains unknown whether or not it provably runs in polynomial time. Other methods for\nsol ving LPs are known to run in so-called weakly polynomial time for general LPs\, but few such results\nare known for the Simplex method even for very restrictive and well-known subclasses of LPs.\n\nIn this talk\, I will di scuss the special subclass of 0/1 LPs\, i.e.\, those whose vertex solution s have\ncomponents in {0\,1}. These are an important and widely studied cl ass of LPs which model many\nproblems from combinatorial optimization. Eve n for this important class\, the performance of the\nSimplex method on the se LPs remained unknown for decades. I will discuss the history of their s tudy as\nit pertains to the Simplex method\, and I will present a series o f results by Alex Black\, Jesús De Loera\,\nLaura Sanità\, and myself wh ich culminate in a proof that the Simplex method can solve 0/1 LPs in\nstr ongly polynomial time.\n LOCATION:https://researchseminars.org/talk/SFUOR/54/ END:VEVENT END:VCALENDAR