Oregon State University

Calendar

Calendars

Event Details

Colloquium: Approximating Disjoint Paths k-Sum Families


Wednesday, January 8, 2014 9:00 AM - 10:00 AM

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.

Additional information: http://eecs.oregonstate.edu/colloquium-series


Kelley Engineering Center (campus map)
1007
Free
Weng-Keen Wong
1 541 737 3617
wong at eecs.oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: