Article contents
Fast approximation of minimum multicast congestion – Implementation VERSUS Theory
Published online by Cambridge University Press: 15 December 2004
Abstract
The problem of minimizing the maximum edge congestion in a multicastcommunication network generalizes the well-known NP-hard multicommodityflow problem. We give the presently best theoretical approximation results aswell as efficient implementations. In particular we show that for a networkwith m edges and k multicast requests, anr(1 + ε)(rOPT + exp(1)lnm)-approximation can be computed inO(kmε-2 lnklnm) time, where β bounds the time forcomputing an r-approximate minimum Steiner tree. Moreover, we present a newfast heuristic that outperforms the primal-dual approaches with respect toboth running time and objective value.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2004
References
- 8
- Cited by