BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20220313T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20221106T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:66e1ddc0a0d00
DTSTART;TZID=America/Toronto:20221125T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20221125T153000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
uium-stefan-weltge
SUMMARY:Tutte Colloquium - Stefan Weltge
CLASS:PUBLIC
DESCRIPTION:Summary \n\nTITLE: Integer programs with bounded subdeterminant
s and two nonzeros\nper row\n\nSpeaker:\n Stefan Weltge\n\nAffiliation:\n
Technical University of Munich\n\nLocation:\n MC 5501 or contact Eva Lee
for Zoom link\n\nABSTRACT: Determining the complexity of integer linear pr
ograms with\ninteger coefficient matrices whose subdeterminants are bounde
d by a\nconstant is currently a very actively discussed question in the fi
eld.\nIn this talk\, I will present a strongly polynomial-time algorithm f
or\nsuch integer programs with the further requirement that every\nconstra
int contains at most two variables. The core of our approach is\nthe first
polynomial-time algorithm for the weighted stable set\nproblem on graphs
that do not contain more than k vertex-disjoint odd\ncycles\, where k is a
ny constant. Previously\, polynomial-time\nalgorithms were only known for
k = 0 (bipartite graphs) and for k = 1.\n\nThis is joint work with Samuel
Fiorini\, Gwenaël Joret\, and Yelena\nYuditsky\, which recently appeared
at FOCS this year.\n
DTSTAMP:20240911T181320Z
END:VEVENT
END:VCALENDAR