
Open access
Date
2003-02Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
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 shortest-path-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. Show more
Permanent link
https://doi.org/10.3929/ethz-a-004517869Publication status
publishedJournal / series
TIK ReportVolume
Publisher
ETH Zurich, Computer Engineering and Networks LaboratoryEdition / version
Version 1Subject
Approximation algorithm; Greedy algorithm; Maximum edge-disjoint paths problem; Shortening lemmaOrganisational unit
02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.
Related publications and datasets
Is previous version of: http://hdl.handle.net/20.500.11850/52575
More
Show all metadata
ETH Bibliography
yes
Altmetrics