Concave generalized flows with applications to market equilibria

Combinatorics Seminar
Friday, September 9, 2011 - 3:05pm
1 hour (actually 50 minutes)
Skiles 005
School of Computer Science, Georgia Tech
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.