Discrete Math Seminar: Bruce Shepherd

  • Date: 06/05/2012
  • Time: 14:30
Bruce Shepherd

Simon Fraser University


Maximum Throughput versus Minimum Congestion in DisjointPath Problems in Planar Graphs




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.

Other Information: 

For more information please visit SFU Mathematics Department