Discrete Math Seminar: Bruce Shepherd

  • Date: 06/05/2012
  • Time: 14:30
Lecturer(s):
Bruce Shepherd
Location: 

Simon Fraser University

Topic: 

Maximum Throughput versus Minimum Congestion in DisjointPath Problems in Planar Graphs

Description: 

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.

Other Information: 

For more information please visit SFU Mathematics Department

Sponsor: