Leírás
EGERVÁRY SZEMINÁRIUM
Absztrakt: 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 at most two nonzero entries
per column. While strongly polynomial algorithms for the primal and
dual feasibility problems have been known for a long time, various
combinatorial approaches used for those problems did not seem to carry
over to the minimum-cost variant.
Our approach is to show that the ‘subspace layered least squares’
interior point method, an earlier joint work with Allamigeon, Dadush,
Loho and Natura requires only a strongly polynomial number of
iterations for minimum cost generalized flow. We achieve this by
bounding the straight line complexity, introduced in the same paper.
The analysis is of combinatorial nature, and no background on interior
point methods is needed. Joint work with Daniel Dadush, Zhuan Khye
Koh, Bento Natura, and Neil Olver.