Concave generalized flows with applications to market equilibria

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