Discrete Math Seminar: Bruce Shepherd

Abstract: 

Garg Vazarani and Yannakakis showed that the integrality gap for (the natural LP relaxation of) maximum disjoint paths (MEDP) in planar graphs is $\\Omega(\\sqrt{n})$. Noting that their gap example (a grid minor) all but disappears if edge congestion 2 is allowed, Kleinberg and Tardos asked if MEDP in planar graphs behaves better when one admits constant congestion. A sequence of results ultimately showed that with constant (in fact 2) congestion, the integrality gap is indeedO(1). ( In addition, recent work of Chuzhoy shows a polylog(n) gap in general graphs with constant congestion.) There are strong connections to a parallel stream of work on routing all demands with minimum congestion. This latter work is on`` flow-cut gaps'' which amounts to embedding a finite metric in L_1.

We discuss the connections and distinctions between the max throughput and min congestion problems, with an emphasis on highlighting some of the open problems.