Daniel Dadush, A Strongly Polynomial Algorithm for Linear Programs with at Most Two Non-Zero Entries per Row or Column
We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Primal and dual feasibility were shown by Végh (MOR ’17) and Megiddo (SICOMP ’83) respectively. Our result can be viewed as …