Fast approximation of minimum multicast congestion – Implementation versus theory

Andreas Baltz; Anand Srivastav

RAIRO - Operations Research - Recherche Opérationnelle (2004)

  • Volume: 38, Issue: 4, page 319-344
  • ISSN: 0399-0559

Abstract

top
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 outperforms the primal-dual approaches with respect to both running time and objective value.

How to cite

top

Baltz, Andreas, and Srivastav, Anand. "Fast approximation of minimum multicast congestion – Implementation versus theory." RAIRO - Operations Research - Recherche Opérationnelle 38.4 (2004): 319-344. <http://eudml.org/doc/245890>.

@article{Baltz2004,
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+\varepsilon )(rtext\{OPT\}+\exp (1)\ln m)$-approximation can be computed in $O(km\varepsilon ^\{-2\}\ln k \ln m)$ time, where $\beta $ 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.},
author = {Baltz, Andreas, Srivastav, Anand},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {combinatorial optimization; approximation algorithms; Combinatorial optimization},
language = {eng},
number = {4},
pages = {319-344},
publisher = {EDP-Sciences},
title = {Fast approximation of minimum multicast congestion – Implementation versus theory},
url = {http://eudml.org/doc/245890},
volume = {38},
year = {2004},
}

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
PB - EDP-Sciences
VL - 38
IS - 4
SP - 319
EP - 344
AB - 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+\varepsilon )(rtext{OPT}+\exp (1)\ln m)$-approximation can be computed in $O(km\varepsilon ^{-2}\ln k \ln m)$ time, where $\beta $ 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.
LA - eng
KW - combinatorial optimization; approximation algorithms; Combinatorial optimization
UR - http://eudml.org/doc/245890
ER -

References

top
  1. [1] J. Aspnes, Y. Azar, A. Fiat, S. Plotkin and O. Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. Association Computing Machinery 44 (1997) 486–504. Zbl0890.68014
  2. [2] R. Carr and S. Vempala, Randomized Metarounding, in Proc. of the 32nd ACM Symposium on the theory of computing (STOC ’00), Portland, USA (2000) 58–62. 
  3. [3] N. Garg, J. Könemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems, in Proc. 39th IEEE Annual Symposium on Foundations of Computer Science (1998) 300–309. Zbl1137.90014
  4. [4] A.V. Goldberg, A natural randomization strategy for multicommodity flow and related algorithms. Inform. Process. Lett. 42 (1992) 249–256. Zbl0773.90026
  5. [5] A.V. Goldberg, A.D. Oldham, S. Plotkin and C. Stein, An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flows, in Proc. 6th Conf. on Integer Prog. and Combinatorial Optimization (1998) 338–352. Zbl0911.90153
  6. [6] M.D. Grigoriadis and L.G. Khachiyan, Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optim. 4 (1994) 86–107. Zbl0808.90105
  7. [7] K. Jansen and H. Zhang, An approximation algorithm for the multicast congestion problem via minimum Steiner trees, in Proc. 3rd Int. Worksh. on Approx. and Random. Alg. in Commun. Netw. (ARANCE’02), Roma, Italy, September 21. Carleton Scientific (2002) 77–90. 
  8. [8] K. Jansen and H. Zhang, Approximation algorithms for general packing problems with modified logarithmic potential function, in Proc. 2nd IFIP Int. Conf. on Theoretical Computer Science (TCS’02), Montréal, Québec, Canada, August 25–30 (2002). 
  9. [9] P. Klein, S. Plotkin, C. Stein and E. Tardos, Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts. SIAM J. Comput. 23 (1994) 466–487. Zbl0809.68077
  10. [10] T. Leighton, F. Makedon, S. Plotkin, C. Stein, E. Tardos and S. Tragoudas, Fast approximation algorithms for multicommodity flow problems. J. Comp. Syst. Sci. 50 (1995) 228–243. Zbl0826.68055
  11. [11] D.W. Matula and F. Shahrokhi, The maximum concurrent flow problem. J. Association Computing Machinery 37 (1990) 318–334. Zbl0696.68071
  12. [12] K. Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs. Inform. Process. Lett. 27 (1998) 125–128. Zbl0635.68071
  13. [13] S. Plotkin, D. Shmoys and E. Tardos, Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20 (1995) 257–301. Zbl0837.90103
  14. [14] T. Radzik, Fast deterministic approximation for the multicommodity flow problem. Math. Prog. 78 (1997) 43–58. Zbl0893.90057
  15. [15] P. Raghavan, Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comp. Syst. Sci. 38 (1994) 683–707. Zbl0659.90066
  16. [16] A. Srivastav and P. Stangier, On complexity, representation and approximation of integral multicommodity flows. Discrete Appl. Math. 99 (2000) 183–208. Zbl0951.68048
  17. [17] S. Vempala and B. Vöcking, Approximating Multicast Congestion, in Proc. 10th ISAAC, Chennai, India (1999) 367–372. Zbl0973.90086
  18. [18] G. Robins and A. Zelikovsky, Improved Steiner tree approximation in graphs, in Proc. of the 11th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2000) (2000) 770–779. Zbl0957.68084

NotesEmbed ?

top

You must be logged in to post comments.