Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions
23 October 2010
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(log log 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(log log n). The best previous result for this problem was a (n1/β,β)approximation for β