# Fast approximation of minimum multicast congestion – Implementation versus theory

- Authors
- Publication Date
- Disciplines

## Abstract

ro04EDP.dvi RAIRO Operations Research RAIRO Oper. Res. 38 (2004) 319–344 DOI: 10.1051/ro:2004028 FAST APPROXIMATION OF MINIMUM MULTICAST CONGESTION – IMPLEMENTATION VERSUS THEORY ∗ Andreas Baltz1 and Anand Srivastav1 Communicated by Rainer E. Burkard Abstract. The problem of minimizing the maximum edge conges- tion 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) lnm)-approximation can be com- puted in O(kmε−2 ln k lnm) time, where β bounds the time for com- puting 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. Keywords. Combinatorial optimization, approximation algorithms. Mathematics Subject Classification. 68W25, 90C27. 1. Introduction A communication network can be modeled as an undirected graph G = (V,E), where each node represents a computer that is able to receive, copy and send packets of data. In multicast traffic, several nodes have a simultaneous demand to receive a copy of a single packet. These nodes together with the packet’s source specify a multicast request S ⊆ V . Meeting the request means to establish a connection represented by a Steiner tree with terminal set S, i.e. a subtree of G ∗ Research of the first author supported by DFG, Grant SR 7/9 – 2. 1 Mathematisches Seminar, Bereich II, Christian-Albrechts-Universita¨t zu Kiel, Christian-Albrechts-Platz 4, D-24118 Kiel, Germany; e-mail: aba;[email protected] c© EDP Sciences 2004 320 A. BALTZ AND A. SRIVASTAV that contains S and has no leaf in V \ S. Given G and a set of multicast requests it is natural to ask about Steiner trees such that the maximum edge congestion, i.e. the maximum number of trees sharing an

## There are no comments yet on this publication. Be the first to share your thoughts.