BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Cedric Koh (UBC Vancouver)
DTSTART:20261117T223000Z
DTEND:20261117T233000Z
DTSTAMP:20261117T011933Z
UID:SFUOR/77
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/SFUOR/77/">A
  Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzer
 o Entries per Row or Column</a>\nby Cedric Koh (UBC Vancouver) as part of 
 PIMS-CORDS SFU Operations Research Seminar\n\nLecture held in ASB 10908.\n
 \nAbstract\nWe give a strongly polynomial algorithm for minimum cost gener
 alized flow\, and as a consequence\, for all linear programs with at most 
 two nonzero entries per row or column. Previously\, strongly polynomial al
 gorithms were only known for the primal and dual feasibility problems. Our
  approach is to show that the path-following interior point method of Alla
 migeon et al. ’22 terminates in a strongly polynomial number of iteratio
 ns for minimum cost generalized flow. We achieve this by bounding the stra
 ight line complexity of the central path\, which is the minimum number of 
 pieces required by a piecewise linear curve to multiplicatively approximat
 e the central path. Based on joint work with Daniel Dadush\, Bento Natura\
 , Neil Olver and László Végh.\n
LOCATION:https://researchseminars.org/talk/SFUOR/77/
END:VEVENT
END:VCALENDAR
