Maximum Edge-Disjoint Paths in $k$-sums of Graphs

Chandra Chekuri, Guyslain Naves, F. Bruce Shepherd

We consider the approximability of the maximum edge-disjoint paths problem (MEDP) in undirected graphs, and in particular, the integrality gap of the natural multicommodity flow ba…