BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Algorithms and Complexity Seminar
SUMMARY:A strongly polynomial algorithm for the minimum-co
st generalized flow problem - Laszlo Vegh (London
School of Economics)
DTSTART;TZID=Europe/London:20240528T130000
DTEND;TZID=Europe/London:20240528T140000
UID:TALK213388AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/213388
DESCRIPTION:We give a strongly polynomial algorithm for minimu
m cost generalized flow and\, as a consequence\, f
or all linear programs with at most two nonzero en
tries per row\, or at most two nonzero entries per
column. Our result can be viewed as progress towa
rds understanding whether all linear programs can
be solved in strongly polynomial time\, also refer
red to as Smale's 9th problem.\n\nOur approach is
based on the recent ‘subspace layered least square
s’ interior point method\, an earlier joint work w
ith Allamigeon\, Dadush\,\nLoho and Natura. They s
how that the number of iterations needed by the IP
M can be bounded in terms of the `straight line co
mplexity’ of the central path. Roughly speaking\,
this is the minimum number of pieces of any piecew
ise linear curve that multiplicatively approximate
s the central path. Our main contribution is a com
binatorial analysis showing that the straight-line
complexity of any minimum cost generalised flow i
nstance is polynomial in the number of arcs and ve
rtices.\n\nThis is joint work with Daniel Dadush\,
Zhuan Khye Koh\, Bento Natura\, and Neil Olver.
LOCATION:Computer Laboratory\, William Gates Building\, Roo
m SS03
CONTACT:Tom Gur
END:VEVENT
END:VCALENDAR