BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Jesus de Loera (UC Davis) DTSTART:20220526T141500Z DTEND:20220526T160000Z DTSTAMP:20260422T065902Z UID:CJCS/72 DESCRIPTION:Title: On Polyhedra Parametrizing ALL pivot rules for the Simplex Method\nby Je sus de Loera (UC Davis) as part of Copenhagen-Jerusalem Combinatorics Semi nar\n\n\nAbstract\nThe simplex method is one of the most famous and popula r algorithms in optimization. The engine of any version of the simplex met hod is a pivot rule that selects the outgoing arc for a current vertex. Pi vot rules come in many forms and types\, but after 80 years we are still i gnorant whether there is one that can make the simplex method run in polyn omial time. This talk is about the polyhedral combinatorics of the simplex method. I will present two recent positive results: For 0/1 polytopes the re are explicit pivot rules for which the number of non-degenerate pivots is polynomial and even linear (joint work with A. Black\, S. Kafer\, L. Sa nita). I also present a parametric analysis for all pívot rules. We cons truct a polytope\, the pivot rule polytope\, that parametrizes all memoryl ess pívot rules of a given LP. Its construction is a generalization of th e Fiber polytope construction of Billera Sturmfels. This is an attempt to get a complete picture of the structure “ space of all pivot rules of an LP” (joint work with A. Black\, N. Lutjeharms\, and R. Sanyal). No pri or knowledge of the simplex method will be assume\, I will only assume the audience loves polytopes.\n LOCATION:https://researchseminars.org/talk/CJCS/72/ END:VEVENT END:VCALENDAR