- This event has passed.
IEOR Seminar Series: Bento Natura, Georgia Tech
November 20, 2023 @ 3:30 pm – 3:45 pm
Title: A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column.
Abstract: We give a strongly polynomial algorithm for minimum cost generalized flow, and hence all linear programs with at most two nonzero entries per row, or at most two nonzero entries per column. This provides a next milestone towards answering Smale’s 9th problem—whether there is a strongly polynomial time algorithm for linear programming in general.
Our approach is to show that the interior point method designed by Allamigeon, Dadush, Loho, Natura, and Végh requires only a strongly polynomial number of iterations for minimum cost generalized flow. We achieve this by bounding the straight line complexity, as introduced in the same paper. Joint work with Daniel Dadush, Zhuan Khye Koh, Neil Olver, and László Végh.
Bio: Bento Natura is a Postdoctoral Fellow at the Simons Institute and Georgia Tech. He received his PhD in Mathematics in 2022 under supervision of László Végh at the London School of Economics. He also holds a B.Sc. and M.Sc. in Mathematics from the University of Bonn. His current research interests are focused on the areas of algorithms, optimization, and game theory.