## 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: