Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: László Végh: Strongly polynomial algorithms for market equilibrium computation

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

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
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.

Document Actions