Combinatorial Optimization Reading Group - Justin Toth

Title: New and Simple Algorithms for Stable Flow Problems

Abstract:

In the previous reading group talk we defined stable flows and saw that they always exist by a reduction to the stable allocation problem. This talk, which is based on the paper of Cseh and Matuschke by the same title, will present a novel augmenting path algorithm for computing stable flows. We will extend these results to stable flows where each edge has a lower and upper bound on the flow that passes on that edge. This extension will yield a simple polynomial time algorithm for stable mathings with forced and forbidden edges.