Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-18T13:46:27.957Z Has data issue: false hasContentIssue false
  • English
  • Français

Fast approximation of minimum multicast congestion – Implementation VERSUS Theory

Published online by Cambridge University Press:  15 December 2004

Andreas Baltz  and
Anand Srivastav
Andreas Baltz
Affiliation:
Mathematisches Seminar, Bereich II, Christian-Albrechts-Universität zu Kiel, Christian-Albrechts-Platz 4, D-24118 Kiel, Germany; [email protected].
Anand Srivastav
Affiliation:
Mathematisches Seminar, Bereich II, Christian-Albrechts-Universität zu Kiel, Christian-Albrechts-Platz 4, D-24118 Kiel, Germany; [email protected].
Get access

Abstract

The problem of minimizing the maximum edge congestion in a multicastcommunication network generalizes the well-known NP-hard multicommodityflow problem. We give the presently best theoretical approximation results aswell as efficient implementations. In particular we show that for a networkwith m edges and k multicast requests, anr(1 + ε)(rOPT + exp(1)lnm)-approximation can be computed inO(kmε-2 lnklnm) time, where β bounds the time forcomputing an r-approximate minimum Steiner tree. Moreover, we present a newfast heuristic that outperforms the primal-dual approaches with respect toboth running time and objective value.

Keywords

Combinatorial optimizationapproximation algorithms.
Type
Research Article
Information
RAIRO - Operations Research , Volume 38 , Issue 4 , October 2004 , pp. 319 - 344
Copyright
© EDP Sciences, 2004

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aspnes, J., Azar, Y., 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. CrossRef
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.
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.
Goldberg, A.V., A natural randomization strategy for multicommodity flow and related algorithms. Inform. Process. Lett. 42 (1992) 249–256. CrossRef
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.
Grigoriadis, M.D. and Khachiyan, L.G., Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optim. 4 (1994) 86–107. CrossRef
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.
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).
Klein, P., Plotkin, S., Stein, C. and Tardos, E., 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. CrossRef
Leighton, T., Makedon, F., Plotkin, S., Stein, C., Tardos, E. and Tragoudas, S., Fast approximation algorithms for multicommodity flow problems. J. Comp. Syst. Sci. 50 (1995) 228–243. CrossRef
Matula, D.W. and Shahrokhi, F., The maximum concurrent flow problem. J. Association Computing Machinery 37 (1990) 318–334.
Mehlhorn, K., A faster approximation algorithm for the Steiner problem in graphs. Inform. Process. Lett. 27 (1998) 125–128. CrossRef
Plotkin, S., Shmoys, D. and Tardos, E., Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20 (1995) 257–301. CrossRef
Radzik, T., Fast deterministic approximation for the multicommodity flow problem. Math. Prog. 78 (1997) 43–58. CrossRef
Raghavan, P., Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comp. Syst. Sci. 38 (1994) 683–707.
Srivastav, A. and Stangier, P., On complexity, representation and approximation of integral multicommodity flows. Discrete Appl. Math. 99 (2000) 183–208. CrossRef
S. Vempala and B. Vöcking, Approximating Multicast Congestion, in Proc. 10th ISAAC, Chennai, India (1999) 367–372.
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.