 |
|
|||
| Authors: | Thomas Erlebach |
| Group: | Theory of Communication Networks |
| Type: | Inproceedings |
| Title: | Maximum Weight EdgeDisjoint Paths in Bidirected Trees |
| Year: | 1999 |
| Pub-Key: | E99a |
| Book Titel: | Communication and Data Management in Large Networks. Workshop of INFORMATIK 99 |
| Pages: | 13-19 |
| Keywords: | edge-disjoint paths |
| Abstract: | Edge-disjoint paths problems are at the heart of resource allocation problems in high-performance communication networks. Tree topologies play a fundamental role in this context. A bidirected tree is the directed graph obtained from an undirected tree if each undirected edge is replaced by two directed edges of opposite directions. Given a set of directed paths in a bidirected tree, where each path is associated with a positive weight, the maximum weight edge-disjoint paths problem is to select a subset of the given paths such that the selected paths are edge-disjoint and the sum of the weights of the selected paths is maximized. This problem is known to be NP-hard even if all weights are equal. We present an approximation algorithm for the problem with arbitrary weights that achieves approximation ratio 8, i.e., it always outputs a solution whose weight is at least one eighth of the optimal weight. Our proof shows that the fractional optimum of the natural LP formulation of the problem is at most eight times as large as the (integral) solution produced by our approximation algorithm.Finally, we can convert our approximation algorithm into an 8.51-approximation algorithm for the maximum weight path coloring problem, which has applications in all-optical WDM networks. |
| Remarks: | Technical Report tr-rsfb-99-066, Universität-Gesamthochschule Paderborn |
| Location: | Paderborn |
| Resources: | [BibTeX] |
