You are here

Approximating Disjoint Paths k-Sum Families

Wednesday, January 8, 2014 -
9:00am to 10:00am
KEC 1007

Speaker Information

Bruce Shepherd
Department of Mathematics and Statistics
McGill University


<p>We discuss the <span data-scayt_word="approximability" data-scaytid="1">approximability</span> 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(\<span data-scayt_word="sqrt" data-scaytid="2">sqrt</span>{n})$ even for planar graphs due to a well-known grid example of <span data-scayt_word="Garg-Vazirani-Yannakakis" data-scaytid="3">Garg-Vazirani-Yannakakis</span>.<br><br> <span data-scayt_word="Kleinberg" data-scaytid="7">Kleinberg</span> and <span data-scayt_word="Tardos" data-scaytid="8">Tardos</span> asked: Is a small gap possible if one allows constant edge congestion? This is indeed possible in two settings (with constant congestion): a <span data-scayt_word="polylog" data-scaytid="9">polylog</span> approximation was shown for general graphs by <span data-scayt_word="Chuzhoy" data-scaytid="10">Chuzhoy</span>, and a constant approximation was shown for planar graphs.<br><br> 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 <span data-scayt_word="CFCC" data-scaytid="12">CFCC</span> property)? The most natural conjecture is that any minor-closed family has the <span data-scayt_word="CCFC" data-scaytid="13">CCFC</span> property.<br><br> 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 <span data-scayt_word="treewidth" data-scaytid="19">treewidth</span> graphs. We show that both classes have the <span data-scayt_word="CFCC" data-scaytid="18">CFCC</span> property. In fact for bounded <span data-scayt_word="treewidth" data-scaytid="20">treewidth</span> graphs we show an O(1)-approximation without edge<br> congestion.</p>

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.