Selected Topics in Algorithms and Optimization (V5C4): Strongly polynomial solvability of linear programs

While linear programming is solvable in polynomial time, such as with the ellipsoid and interior point methods, a fundamental question remains open: does there exist a strongly polynomial algorithm, i.e., one where the number of arithmetic operations is polynomial in the number of variables and constraints? The existence of such an algorithm was listed as one of the most significant challenges for 21st century mathematics by the Field medalist Steven Smale. The course gives an overview of classical and recent results towards this question. 

The course will start with classical variable fixing, scaling and parametric search techniques for network optimization problems. We will also cover the theory of combinatorial interior point methods, a powerful approach combining continuous and discrete optimization techniques, that provides a unified framework to several previous strongly polynomial algorithms, as well as led to new results. This includes a recent result by Dadush, Koh, Natura, Olver, and Végh on developing a strongly polynomial algorithm for linear programs with at most two nonzero variables per column.

The course will be given in English; lecture notes will be available. Sources for the course will include the following textbooks and articles:

·      Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1988). Network flows.

·      Grötschel, M., Lovász, L., & Schrijver, A. (2012). Geometric algorithms and combinatorial optimization (Vol. 2). Springer.

·      Tardos, É. (1986). A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research, 34(2), 250-256.

·      Ekbatani, F., Natura, B., & Végh, L. A. (2022). Circuit imbalance measures and linear programming. Surveys in combinatorics, 64-114.

·      Olver, N., & Végh, L. A. (2020). A simpler and faster strongly polynomial algorithm for generalized flow maximization. Journal of the ACM (JACM), 67(2), 1-26.

·      Allamigeon, X., Dadush, D., Loho, G., Natura, B., & Végh, L. A. (2025). Interior point methods are not worse than Simplex. SIAM Journal on Computing, 2025.

·      Dadush, D., Koh, Z. K., Natura, B., Olver, N., & Végh, L. A. (2024, June). A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (pp. 1561-1572).