Theory of Computing
-------------------
Title     : An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow
Authors   : Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd
Volume    : 2
Number    : 7
Pages     : 137-146
URL       : https://theoryofcomputing.org/articles/v002a007

Abstract
--------
  We consider the maximization version of the edge-disjoint 
  path problem (EDP). In undirected graphs and directed 
  acyclic graphs, we obtain an  O(sqrt n)  upper bound on 
  the approximation ratio where  n  is the number of nodes 
  in the graph. We show this by establishing the upper bound
  on the integrality gap of the natural relaxation based on 
  multicommodity flows. Our upper bound matches within a 
  constant factor a lower bound of  Omega(sqrt n)  that
  is known for both undirected and directed acyclic graphs.
  The best previous upper bounds on the integrality gaps were
  O(min{n^{2/3}, sqrt{m}}) for undirected graphs and 
  O(min{sqrt{n log n}, sqrt{m}})  for directed acyclic graphs;
  here  m  is the number of edges in the graph. These bounds 
  are also the best known approximation ratios for these problems.
  Our bound also extends to the unsplittable flow problem (UFP) 
  when the maximum demand is at most the minimum capacity.