BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:A strongly polynomial algorithm for the minimum-cost generalized f
 low problem - Laszlo Vegh (London School of Economics)
DTSTART:20240528T120000Z
DTEND:20240528T130000Z
UID:TALK213388@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:We 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 at most two nonzero entries per column. O
 ur result can be viewed as progress towards understanding whether all line
 ar programs can be solved in strongly polynomial time\, also referred to a
 s Smale's 9th problem.\n\nOur approach is based on the recent ‘subspace 
 layered least squares’ interior point method\, an earlier joint work wit
 h Allamigeon\, Dadush\,\nLoho and Natura. They show that the number of ite
 rations needed by the IPM can be bounded in terms of the `straight line co
 mplexity’ of the central path. Roughly speaking\, this is the minimum nu
 mber of pieces of any piecewise linear curve that multiplicatively approxi
 mates the central path. Our main contribution is a combinatorial analysis 
 showing that the straight-line complexity of any minimum cost generalised 
 flow instance is polynomial in the number of arcs and vertices.\n\nThis is
  joint work with Daniel Dadush\, Zhuan Khye Koh\, Bento Natura\, and Neil 
 Olver.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR