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:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69dad9615d7cb
DTSTART;TZID=America/Toronto:20240920T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240920T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-bento-natura
SUMMARY:Tutte colloquium-Bento Natura
CLASS:PUBLIC
DESCRIPTION:A strongly polynomial algorithm for linear programs with at mos
 t two\nnon-zero entries per row or column.\n\nSpeaker\n Bento Natura\n\nAf
 filiation\n Columbia University\n\nLocation\n MC 5501\n\nABSTRACT:We give 
 a strongly polynomial algorithm for minimum cost\ngeneralized flow\, and h
 ence for optimizing any linear program with at\nmost two non-zero entries 
 per row\, or at most two non-zero entries per\ncolumn. Primal and dual fea
 sibility were shown by Megiddo (SICOMP '83)\nand Végh (MOR '17) respectiv
 ely. Our result can be viewed as progress\ntowards understanding whether a
 ll linear programs can be solved in\nstrongly polynomial time\, also refer
 red to as Smale's 9th problem. Our\napproach is based on the recent primal
 -dual interior point method\n(IPM) due to Allamigeon\, Dadush\, Loho\, Nat
 ura and Végh (FOCS '22).\nThe number of iterations needed by the IPM is b
 ounded\, up to a\npolynomial factor in the number of inequalities\, by the
  straight line\ncomplexity of the central path. Roughly speaking\, this is
  the minimum\nnumber of pieces of any piecewise linear curve that multipli
 catively\napproximates the central path. As our main contribution\, we sho
 w that\nthe straight line complexity of any minimum cost generalized flow\
 ninstance is polynomial in the number of arcs and vertices. By applying\na
  reduction of Hochbaum (ORL '04)\, the same bound applies to any\nlinear p
 rogram with at most two non-zeros per column or per row. To be\nable to ru
 n the IPM\, one requires a suitable initial point. For this\npurpose\, we 
 develop a novel multistage approach\, where each stage can\nbe solved in s
 trongly polynomial time given the result of the previous\nstage. Beyond th
 is\, substantial work is needed to ensure that the bit\ncomplexity of each
  iterate remains bounded during the execution of the\nalgorithm. For this 
 purpose\, we show that one can maintain a\nrepresentation of the iterates 
 as a low complexity convex combination\nof vertices. Our approach is black
 -box and can be applied to any\nlog-barrier path following method. \n\nBe
 nto Natura is an Assistant Professor in Industrial Engineering and\nOperat
 ions Research (IEOR) at Columbia University. He spent two years\nas a Post
 doctoral Fellow at Georgia Tech\, Brown University\, and UC\nBerkeley. Pri
 or to that\, he obtained his PhD in Mathematics from the\nLondon School of
  Economics.\n\nHis research interests are focused on the areas of algorith
 ms\,\noptimization\, and game theory\, with a special emphasis on the theo
 ry\nof linear programming.
DTSTAMP:20260411T232937Z
END:VEVENT
END:VCALENDAR