April 17, 2023: ACO Alumni Lecture featuring Daniel Dadush
Dr. Dadush is currently a senior researcher at CWI in Amsterdam, where he leads the Networks & Optimization group. He received his PhD at Georgia Tech in 2012 in Algorithms, Combinatorics and Optimization, and was a Simons postdoctoral researcher at NYU before joining CWI in 2014. He won the first ACO outstanding student prize (2012), and the A. W. Tucker Prize of the Mathematical Optimization Society in 2015. His research interests include linear and integer programming, discrepancy minimization and high dimensional convex geometry. While an ACO student at GT, he initiated the ACO student seminar, which has been running continuously since its inception.
ACO Alumni Lecture Title: Interior point methods are not worse than Simplex
Klaus 1116, 11am, Monday, April 17th.
Abstract : Whereas 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 classical simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound O(2^n n^{1.5} log n) for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations. The number of iterations of our algorithm is at most O(n^{1.5} log n) times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the ‘max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of n shadow vertex simplex paths. This is joint work with Xavier Allamigeon (INRIA / Ecole Polytechnique), Georg Loho (U. Twente), Bento Natura (LSE), Laszlo Vegh (LSE).
