OREGON STATE UNIVERSITY

You are here

Approximating Disjoint Paths k-Sum Families

KEC 1007
Wednesday, January 8, 2014 - 9:00am to 10:00am
Speaker Information
Bruce Shepherd
Professor
Department of Mathematics and Statistics
McGill University

We discuss the approximability of the maximum edge-disjoint paths problem in undirected graphs, which is closely linked to the integrality gap for its natural multi-commodity flow based relaxation. This gap is known to be $\Omega(\sqrt{n})$ even for planar graphs due to a well-known grid example of Garg-Vazirani-Yannakakis.

Kleinberg and Tardos asked: Is a small gap possible if one allows constant edge congestion? This is indeed possible in two settings (with constant congestion): a polylog approximation was shown for general graphs by Chuzhoy, and a constant approximation was shown for planar graphs.

Two interesting directions remain open. (A) Can edge congestion can be avoided with a stronger LP formulation? And (B) For which graph families is there an O(1)-integrality gap with constant edge-congestion (called the CFCC property)? The most natural conjecture is that any minor-closed family has the CCFC property.

Given that Robertson and Seymour's characterization for minor-closed families involves k-sums of bounded genus graphs, two building blocks must be the families of bounded genus graphs and bounded treewidth graphs. We show that both classes have the CFCC property. In fact for bounded treewidth graphs we show an O(1)-approximation without edge
congestion.

Speaker Bio

Bruce Shepherd completed an M.Math. (1987) and Ph.D. (1990) in C&O after completing a combined Mathematics and Computer Science B.Sc. at the University of Victoria. His Master's thesis was in Graph Theory under the supervision of Dan Younger, and his PhD thesis was in Polyhedral Combinatorics under the supervision of William Pulleyblank. During his doctoral work he also produced train scheduling software with Pulleyblank for Canadian Pacific Railway (CPR). He went on to hold a NATO Postdoctoral Fellowship working with Lex Schrijver in CWI, Amsterdam and a Von Humboldt Fellowship working with Bernhard Korte in Bonn.

His first academic appointment in 1992 was joint between Math and Operational Research at the London School of Economics. During that time he also performed consulting in Optimization for firms such as British Telecom, Rio-Tinto, and Reuters. In 1997 he joined Bell Labs in Murray Hill, NJ where he continued to divide his time between applications of optimization and the fundamental theory of Combinatorial Optimization. He designed algorithms and produced software in areas such as optical network design, real-time network management, scheduling and internet measurement. He also kept a healthy interest in the theory behind these  problems including producing the first model (with Griffin and Wilfong) for the analysis of the world's defacto interdomain routing protocol BGP. With the exception of 2011-12, which he spent in the Theory Group at Microsoft Research, he has held the position of James McGill Professor (internal equivalent of a Tier 1 Canada Research Chair) in the Department of Mathematics and Statistics at McGill University since 2007.