Trees, Flows, and Clusters
Speaker:
Bruce Shepherd, McGill University
Date and Time:
Friday, June 3, 2016 - 5:00pm to 5:30pm
Location:
Fields Institute, Room 230
Abstract:
Tree structures have appeared persistently both in the models and algorithms for combinatorial optimization. Not surprisingly, there is an associated well-developed toolkit for these problems. It is perhaps surprising that the classical model of flows in networks (aka Max-flow Min-cut) admits several natural open questions when the flows must be routed on a tree: so-called confluent flows. We discuss a solution for one of those questions and explain connections to IP routing, rooted clustering and stable matchings