Fast approximation of minimum multicast congestion – implementation versus theory

Fast approximation of minimum multicast congestion – implementation versus theory

0.00 Avg rating0 Votes
Article ID: iaor20052772
Country: France
Volume: 38
Issue: 4
Start Page Number: 319
End Page Number: 344
Publication Date: Oct 2004
Journal: RAIRO Operations Research
Authors: ,
Keywords: programming (combinatorial)
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(l + ϵ) (rOPT + exp(1) ln m)-approximation can be computed in O(kmϵ-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.

Reviews

Required fields are marked *. Your email address will not be published.