04-10   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Andreas Baltz, Anand Srivastav:

Fast Approximation of Minimum Multicast Congestion - Implementation versus Theory

The problem of minimizing the maximum edge congestion in a multicast communication network generalizes the well-known NP-hard multicommodity flow problem. We give the presently best theoretical approximation results as well as efficient implementations. In particular we show that for a network with m edges and k multicast requests, an

r(1+ε)(rOPT + exp(1) ln m)-approximation

can be computed in

O( k m ε^{-2} ln k ln m) time,

where ε bounds the time for computing an r-approximate minimum Steiner tree. Moreover, we present a new fast heuristic that outperforms the primal-dual approaches with respect to both running time and objective value.

Mathematics Subject Classification (1991): 68W25, 90C27

Keywords: combinatorial optimization, approximation algorithms

Mail an Jens Burmeister
[Thu Feb 19 18:56:36 2009]
Impressum