Fast approximation of minimum multicast congestion – Implementation VERSUS Theory

¹ Mathematisches Seminar, Bereich II, Christian-Albrechts-Universität zu Kiel, Christian-Albrechts-Platz 4, D-24118 Kiel, Germany; aba@numerik.uni-kiel.de.
² Mathematisches Seminar, Bereich II, Christian-Albrechts-Universität zu Kiel, Christian-Albrechts-Platz 4, D-24118 Kiel, Germany; asr@numerik.uni-kiel.de.

Abstract

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)lnm)-approximation can be computed in O(kmε^-2lnklnm) 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.