Breaking o(n 1/2 )-approximation algorithms for the edge-disjoint paths problem with congestion two
Ken‐ichi Kawarabayashi, Yusuke Kobayashi · 2011
In the maximum edge-disjoint paths problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be routed by edge-disjoint paths. An r-approximation algorithm for this problem is a polynomial time algorithm that finds at least OPT / r edge-disjoint paths, where OPT is the maximum possible. Currently, an O(n1/2)-approximation algorithm is best known for this problem even if a congestion of two is allowed, i.e., each edge is allowed to be used in at most two of the paths.