PIMS-UVic Distinguished Lecture: Bruce Shepherd

Title: Trees, Flows and Rooted Clusters

Speaker: Bruce Shepherd, McGill University

Date and time: 02 Feb 2016, 1:30pm - 3:00pm

Location: Cornett Building, room A221

Event type: PIMS lectures


LECTURE: 2:00 – 3:00 pm

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.

Download poster (pdf) 

Members of Mathematics/Statistics please note that there will be a brief reception at the University Club at 3:30 pm put on by the Faculty of Science to honour Bruce Shepherd, winner of the UVic Distinguished Alumni Award for the Faculty of Science.  Alumni will also be in attendance.

Shepherd, who completed a BSc in Computer Science and Mathematics at the University of Victoria in 1985, will be honoured along with other distinguished alumni at an award ceremony Tuesday evening, February 2nd.

Bruce Shepherd is a member of the Department of Mathematics and Statistics, McGill University where he has held the position of James McGill Professor (internal equivalent of a Tier 1 Canada Research Chair) since 2007. He is also an associate member of McGill's School of Computer Science

Dr. Shepherd completed a BSc in Computer Science and Mathematics at the University of Victoria and then studied at the University of Waterloo where he earned his MSc and Ph.D. in Department of Combinatorics and Optimization. During his doctoral studies he also worked with his advisor William Pulleyblank to produce train scheduling software for the meet-pass problem at Canadian Pacific Railway. He went on to hold a NATO Postdoctoral Fellowship working with Lex Schrijver in CWI, Amsterdam and a Von Humboldt Fellowship at the University of Bonn.

His first academic appointment in 1992 was joint between Mathematics and Operational Research at the London School of Economics. During that time be performed consulting in optimization for firms such as British Telecom, Rio Tinto, and Reuters. He was also codirector of the LSE Centre for Discrete and Applicable Mathematics and was co-founder (with Jean Fonlupt and Bernhard Korte) of the Discrete Optimization Network (DONET) which was a European initiative, lasting over a decade, supporting research and practice in optimization.

In 1997 he joined Bell Laboratories, Murray Hill, NJ where he designed algorithms and produced software which was deployed in products for optical network design, real-time network management, scheduling and internet measurement. He also maintained an interest in the fundamental theory behind these problems including his work with Tim Griffin and Gordon Wilfong which formulated a graph theory model to analyze the world's defacto interdomain routing protocol BOP.

Dr. Shepherd has spent leaves at the Theory Group of Microsoft Research, the Department of Computer Science, University of Washington (2011-12) and the Sauder School of Management, UBC (2014), as well as long-term visits to the Fields Institute, University of Bonn, DIMACS, and University of Tokyo. He currently sits on the board of two of the foremost journals in mathematical optimization: Mathematical Programming Series A where he is a coeditor, and Mathematical Programming Computation where he is an area editor.