Affordable Access

Fast approximation of minimum multicast congestion – Implementation versus theory

Publication Date
  • Communication
  • Computer Science


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.