Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We study the Edge-Disjoint Paths with Congestion (EDPwC) problem in undirected networks in which we must integrally route a set of demands without causing large congestion on an edge. We present a $(polylog(n),poly(loglog n)))$-approximation, which means that if there exists a solution that routes $X$ demands integrally on edge-disjoint paths (i.e. with congestion $1$), then the approximation algorithm can route $X/polylog(n)$ demands with congestion $poly(loglog n)$.

The best previous result for this problem was a $(n^{1/eta},eta)$-approximation for $eta<log n$.

Questions and Answers

You need to be logged in to be able to post here.