Combinatorial Optimization Reading Group - Sharat Ibrahimpur

Friday, July 19, 2019 1:00 pm - 1:00 pm EDT (GMT -04:00)

Title: Stable Flows

Speaker: Sharat Ibrahimpur
Affiliation: University of Waterloo
Room: MC 5479


We describe a flow model that generalizes ordinary network flows the same way as stable matchings generalize the bipartite matching problem. We prove that there always exists a stable flow and generalize the lattice structure of stable marriages to stable flows. We show a straightforward reduction of the stable flow problem to finding stable allocations. This talk is based on the paper entitled On Stable Matchings and Flows by Tamas Fleiner. 

The talk will be self-contained.