|
Speaker: Bento Natura (Columbia) “Faster Exact Linear Programming” Wednesday, September 25, 2024 11:30 am: Lunch (Kitchen) 12:00 pm: Talk (Seminar Room #1327) |
Add To: Google Calendar | Outlook | iCal File
Optional Zoom link: https://yale.zoom.us/j/99342713421
Abstract: We present a novel algorithm to solve various subclasses of linear programs, with a particular focus on strongly polynomial algorithms—those that operate in polynomial time relative to the problem’s dimension. Although subclasses like bipartite matching and maximum flow are known to be solvable in strongly polynomial time, the existence of such algorithms for general linear programs remains one of the most challenging open questions in discrete mathematics and beyond. While not achieving a solution for general linear programs, we introduce a new algorithm that recovers strong polynomiality for many subclasses and resolves the long-standing open problem of whether linear programs with at most two variables per row or column can be solved in strongly polynomial time. This algorithm is competitive with any algorithm in the extensive theory of path-following methods in linear programming.
Bio: Bento Natura is an Assistant Professor 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.
His research interests are focused on the areas of algorithms, optimization, and game theory, with a special emphasis on the theory of linear programming.
