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:686a3ccf21c3d
DTSTART;TZID=America/Toronto:20240920T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240920T163000
URL:/combinatorics-and-optimization/events/tutte-colloq
 uium-bento-natura
SUMMARY:Tutte colloquium-Bento Natura
CLASS:PUBLIC
DESCRIPTION:Summary \n\nA strongly polynomial algorithm for linear programs
  with at most two\nnon-zero entries per row or column.\n\nSpeaker\n Bento 
 Natura\n\nAffiliation\n Columbia University\n\nLocation\n MC 5501\n\nABSTR
 ACT:We give a strongly polynomial algorithm for minimum cost\ngeneralized 
 flow\, and hence for optimizing any linear program with at\nmost two non-z
 ero entries per row\, or at most two non-zero entries per\ncolumn. Primal 
 and dual feasibility were shown by Megiddo (SICOMP '83)\nand Végh (MOR '1
 7) respectively. Our result can be viewed as progress\ntowards understandi
 ng whether all linear programs can be solved in\nstrongly polynomial time\
 , also referred to as Smale's 9th problem. Our\napproach is based on the r
 ecent primal-dual interior point method\n(IPM) due to Allamigeon\, Dadush\
 , Loho\, Natura and Végh (FOCS '22).\nThe number of iterations needed by 
 the IPM is bounded\, up to a\npolynomial factor in the number of inequalit
 ies\, by the straight line\ncomplexity of the central path. Roughly speaki
 ng\, this is the minimum\nnumber of pieces of any piecewise linear curve t
 hat multiplicatively\napproximates the central path. As our main contribut
 ion\, we show that\nthe straight line complexity of any minimum cost gener
 alized flow\ninstance is polynomial in the number of arcs and vertices. By
  applying\na reduction of Hochbaum (ORL '04)\, the same bound applies to a
 ny\nlinear program with at most two non-zeros per column or per row. To be
 \nable to run the IPM\, one requires a suitable initial point. For this\np
 urpose\, we develop a novel multistage approach\, where each stage can\nbe
  solved in strongly polynomial time given the result of the previous\nstag
 e. Beyond this\, substantial work is needed to ensure that the bit\ncomple
 xity of each iterate remains bounded during the execution of the\nalgorith
 m. For this purpose\, we show that one can maintain a\nrepresentation of t
 he iterates as a low complexity convex combination\nof vertices. Our appro
 ach is black-box and can be applied to any\nlog-barrier path following met
 hod. \n\nBento Natura is an Assistant Professor in Industrial Engineering
  and\nOperations Research (IEOR) at Columbia University. He spent two year
 s\nas a Postdoctoral Fellow at Georgia Tech\, Brown University\, and UC\nB
 erkeley. Prior to that\, he obtained his PhD in Mathematics from the\nLond
 on School of Economics.\n\nHis research interests are focused on the areas
  of algorithms\,\noptimization\, and game theory\, with a special emphasis
  on the theory\nof linear programming.\n 
DTSTAMP:20250706T090727Z
END:VEVENT
END:VCALENDAR