Page 1

Displaying 1 – 3 of 3

Showing per page

Fast approximation of minimum multicast congestion – Implementation versus theory

Andreas Baltz, Anand Srivastav (2004)

RAIRO - Operations Research - Recherche Opérationnelle

The problem of minimizing the maximum edge congestion in a multicast communication network generalizes the well-known N P -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 + ε ) ( r t e x t O P T + exp ( 1 ) ln m ) -approximation can be computed in O ( k m ε - 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...

Fast approximation of minimum multicast congestion – Implementation VERSUS Theory

Andreas Baltz, Anand Srivastav (2010)

RAIRO - Operations Research

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,...

Currently displaying 1 – 3 of 3

Page 1