Greedy-edge-disjoint paths in complete graphs
Paz Carmi, Thomas Erlebach, Yoshio Okamoto · Repository for Publications and Research Data (ETH Zurich) · 2003
The maximum edge-disjoint paths problem (MEDP) is one of the most classical NP-hard problems.We study the approximation ratio of a simple and practical approximation algorithm, the shortestpath-first greedy algorithm (SGA), for MEDP in complete graphs.Previously, it was known that this ratio is at most 54.Adapting results by Kolman and Scheideler [Proceedings of SODA, 2002, pp.184-193], we show that SGA achieves approximation ratio 8F + 1 for MEDP in undirected graphs with flow number F and, therefore, has approximation ratio at most 9 in complete graphs.Furthermore, we construct a family of instances that shows that SGA cannot be better than a 3-approximation algorithm.Our upper and lower bounds hold also for the bounded-length greedy algorithm, a simple on-line algorithm for MEDP.