BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:America/New_York
X-WR-TIMEZONE:America/New_York
BEGIN:VEVENT
UID:633@fds.yale.edu
DTSTART;TZID=America/New_York:20240925T113000
DTEND;TZID=America/New_York:20240925T133000
DTSTAMP:20250916T142138Z
URL:https://fds.yale.edu/events/fds-colloquium-bento-natura-faster-exact-l
 inear-programming/
SUMMARY:FDS Colloquium: Bento Natura (Columbia)\, "Faster Exact Linear Prog
 ramming"
DESCRIPTION:Optional Zoom link:  https://yale.zoom.us/j/99342713421\n\n\n\n
 Abstract: We present a novel algorithm to solve various subclasses of line
 ar programs\, with a particular focus on strongly polynomial algorithms—
 those that operate in polynomial time relative to the problem’s dimensio
 n. Although subclasses like bipartite matching and maximum flow are known 
 to be solvable in strongly polynomial time\, the existence of such algorit
 hms for general linear programs remains one of the most challenging open q
 uestions in discrete mathematics and beyond. While not achieving a solutio
 n for general linear programs\, we introduce a new algorithm that recovers
  strong polynomiality for many subclasses and resolves the long-standing o
 pen problem of whether linear programs with at most two variables per row 
 or column can be solved in strongly polynomial time. This algorithm is com
 petitive with any algorithm in the extensive theory of path-following meth
 ods in linear programming.\n\n\n\nBio: Bento Natura is an Assistant Profe
 ssor in Industrial Engineering and Operations Research (IEOR) at Columbia 
 University. He spent two years as a Postdoctoral Fellow at Georgia Tech\, 
 Brown University\, and UC Berkeley. Prior to that\, he obtained his PhD in
  Mathematics from the London School of Economics.\n\n\n\nHis research inte
 rests are focused on the areas of algorithms\, optimization\, and game the
 ory\, with a special emphasis on the theory of linear programming.\n
CATEGORIES:FDS Events,Colloquium
END:VEVENT
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:DAYLIGHT
DTSTART:20240310T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR