Geodesic
Fast approximation of minimum multicast congestion - Implementation versus theory
RAIRO - Operations Research - Recherche Opérationnelle, Tome 38 (2004) no. 4, pp. 319-344

Voir la notice de l'article provenant de la source Numdam

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

DOI : 10.1051/ro:2004028
Classification : 68W25, 90C27
Keywords: combinatorial optimization, approximation algorithms 
@article{RO_2004__38_4_319_0,
     author = {Baltz, Andreas and Srivastav, Anand},
     title = {Fast approximation of minimum multicast congestion - {Implementation} versus theory},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {319--344},
     publisher = {EDP-Sciences},
     volume = {38},
     number = {4},
     year = {2004},
     doi = {10.1051/ro:2004028},
     zbl = {1114.90101},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2004028/}
}
TY  - JOUR
AU  - Baltz, Andreas
AU  - Srivastav, Anand
TI  - Fast approximation of minimum multicast congestion - Implementation versus theory
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2004
SP  - 319
EP  - 344
VL  - 38
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro:2004028/
DO  - 10.1051/ro:2004028
LA  - en
ID  - RO_2004__38_4_319_0
ER  - 
%0 Journal Article
%A Baltz, Andreas
%A Srivastav, Anand
%T Fast approximation of minimum multicast congestion - Implementation versus theory
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2004
%P 319-344
%V 38
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro:2004028/
%R 10.1051/ro:2004028
%G en
%F RO_2004__38_4_319_0
Baltz, Andreas; Srivastav, Anand. Fast approximation of minimum multicast congestion - Implementation versus theory. RAIRO - Operations Research - Recherche Opérationnelle, Tome 38 (2004) no. 4, pp. 319-344. doi: 10.1051/ro:2004028

Cité par Sources :