A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column

Cedric Koh (UBC Vancouver)

Tue Nov 17, 22:30-23:30 (starts in 21 hours)
Lecture held in ASB 10908.

Abstract: 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 Allamigeon et al. ’22 terminates in a strongly polynomial number of iterations for minimum cost generalized flow. We achieve this by bounding the straight line complexity of the central path, which is the minimum number of pieces required by a piecewise linear curve to multiplicatively approximate the central path. Based on joint work with Daniel Dadush, Bento Natura, Neil Olver and László Végh.

Mathematics

Audience: researchers in the topic


PIMS-CORDS SFU Operations Research Seminar

Organizer: Tamon Stephen*
*contact for this listing

Export talk to