LFCS Seminar: 4 December 2018 - László Végh

Title: Strongly polynomial algorithms for market equilibrium computation

Abstract:

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.