Georgia Tech SCL Georgia Tech SCL Georgia Tech SCL

Title:       

Recent Advances in Strongly Polynomial Algorithms for Linear Programming

Abstract:

Whereas ellipsoid methods and interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. 

An important unresolved question in operations research, theoretical computer science, and related fields, concerns the existence of a strongly polynomial algorithm for linear programming. Such an algorithm's running time would solely depend on the problem's dimension and the number of constraints, independent of any additional condition numbers. This question, first articulated by Megiddo in the 1980s, has gained prominence as Smale's 9th problem.

In the first part of our talk, we introduce a new polynomial-time path-following interior point method where the number of iterations admits a combinatorial upper bound that is exponential in the number of constraints. More precisely, the iteration count of our algorithm is at most a small polynomial factor times the segment count of any piecewise linear trajectory within a wide neighborhood of the central path. Notably, it parallels the iteration count of any path-following interior point method, with an adjustment for this polynomial factor.

In the second part of our talk, 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.

Bio:

Bento Natura is a Ronald J. and Carol T. Beerman/ARC Postdoctoral Fellow in ISyE at Georgia Tech. He obtained his PhD in the Department of Mathematics at the London School of Economics, where he was supervised by László Végh. His doctoral thesis earned him the departmental Dissertation Prize and placed as a runner-up for the PhD Prize awarded by the OR Society of the United Kingdom. Prior to his PhD, Bento earned Bachelor's and Master's degrees in Mathematics from the University of Bonn, under the supervision of Stephan Held and Jens Vygen. Bento's current research interests are centered on algorithms, optimization, and game theory.