Approximating Disjoint Paths k-Sum Families
Wednesday, January 8, 2014 - 9:00am - 10:00am
KEC 1007
Bruce Shepherd
Professor
Department of Mathematics and Statistics
McGill University
Abstract:
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 Biography:
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 Depa!
rtment of Mathematics and Statistics at McGill University since 2007.
_______________________________________________
Colloquium mailing list
[email protected]
https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
