A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column
–
We give a strongly polynomial algorithm for minimum cost generalized flow, and as a consequence, for all linear programs with at most two nonzero entries per row or column. Previously, strongly polynomial algorithms were only known for the primal and dual feasibility problems. Our approach is to show that the path-following interior point method of […]