BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Eurandom - ECPv5.9.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Eurandom
X-ORIGINAL-URL:https://www.eurandom.tue.nl
X-WR-CALDESC:Events for Eurandom
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20210601T154500
DTEND;TZID=UTC:20210601T164500
DTSTAMP:20211015T203759
CREATED:20210519T120352Z
LAST-MODIFIED:20210602T075355Z
UID:4035-1622562300-1622565900@www.eurandom.tue.nl
SUMMARY:Eindhoven Stochastic Seminar
DESCRIPTION:Ahmad Abdi (LSE) \nIdeal matrices and dyadic linear programming \nA 0\,1 matrix M is ideal if the set cover inequalities Mx>=1\, together with nonnegativity constraints x>=0\, define a polyhedron where every vertex is integral. The study of ideal matrices was initiated in the 1960s by Alfred Lehman and Ray Fulkerson\, and continues to this day due to their intimate connections to Integer Programming\, Combinatorial Optimization\, and Graph Theory. Despite having being studied for about 60 years\, several basic questions about them remain open to this day. In this talk\, I will discuss some of these questions. \nGiven an ideal matrix M\, consider the set covering linear program min{1Tx: Mx>=1\,x>=0} and its dual max{1Ty : MT y <= 1\, y>=0}. The notion of idealness certifies that the primal linear program has an integral optimal solution. If the dual had an integral optimal solution\, too\, it would lead to a beautiful min-max relation\, extending many classical ones such as Menger’s and König’s Theorems. Unfortunately\, this is not the case\, but an old conjecture by Paul Seymour from 1975 predicts that the dual has an optimal solution whose entries are dyadic rationals\, i.e. whose entries have an exact floating point representation. \nIn this talk\, I will motivate this conjecture\, discuss its potential applications to theory and practice\, and discuss how Minor Theory has led to a proof of the conjecture when the dual has optimal value 2. Based on joint work with Gérard Cornuéjols\, Bertrand Guenin\, and Levent Tunçel. \nVIDEOSTREAM
URL:https://www.eurandom.tue.nl/event/eindhoven-stochastic-seminar-15/
LOCATION:MS Teams
END:VEVENT
END:VCALENDAR