LFCS seminar: László Végh: Strongly polynomial algorithms for market equilibrium computation
What 


When 
Dec 04, 2018 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
Most known strongly polynomial algorithms are for special classes of linear programs, and only few examples are known in nonlinear optimization. The talk will give an overview of two such results. The first result gives a strongly polynomial algorithm for some instances of flows with separable convex objectives, including separable convex quadratic objectives, as well as market equilibrium in linear Fisher markets. The second, more recent result provides the first strongly polynomial algorithm for exchange markets with linear utilities. These results can be obtained by extending the classical technique of variable fixing from linear programs to the convex settings. The main progress in both algorithms is gradually identifying edges in the support of the optimal solutions. This is based on joint work with Jugal Garg.