Concave generalized flows with applications to market equilibria

Series
Combinatorics Seminar
Time
Friday, September 9, 2011 - 3:05pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Laszlo Vegh – School of Computer Science, Georgia Tech – veghal@gmail.com
Organizer
Prasad Tetali
The generalized flow model is a classical and widely applicable extension of network flows, where on every arc, the flow leaving the arc is a linear function of the flow entering the arc. In the talk, I will investigate a nonlinear extension of this model, with the flow leaving an arc being a concave function of the entering flow. I exhibit the first combinatorial polynomial time algorithm for solving corresponding optimization problems. This model turns out to be a common framework for solving several market equilibrium problems, such as linear Fisher markets, and immediately enables to extend them to more general settings. I will also give a survey on generalized flow algorithms and previous nonlinear flow models.