PIMS-UVic Distinguished Lecture: Bruce Shepherd

We first give an accessible overview of combinatorial optimization and highlight the role of mathematics and theoretical computer science in developing efficient solution techniques. 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.