On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths
DOI:
https://doi.org/10.2298/YJOR181015034BKeywords:
computational experiment, linear programming, fully polynomial-time approximation scheme, greedy heuristic, software defined satellite networkAbstract
The paper presents a comparison between three approaches to solving the length-bounded maximum multicommodity flow problem with unit edge-lengths. Following the first approach, Garg and Könemann’s, we developed an improved fully polynomial time approximation scheme for this problem. As the second alternative, we considered the well-known greedy approach. The third approach is the one that yields exact solutions by means of a standard LP solver applied to an LP model on the time-expanded network. Computational experiments are carried out on benchmark graphs and the graphs that model software defined satellite networks, to compare the proposed algorithms with an exact linear programming solver. The results of the experiments demonstrate a trade-off between the computing time and the precision of algorithms under consideration.References
Albrecht, Ch., “Global routing by new approximation algorithms for multicommodity flow”, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 20 (5) (2001) 622–632.
Asano, Y., Experimental Evaluation of Approximation Algorithms for the Minimum Cost Multiple-source Unsplittable Flow Problem, in: ICALP Satellite Workshops, Carleton Scientific, Waterloo, Ontario, Canada, 2000, 111–122.
Baier, G., Flows with Path Restrictions, Ph.D. Diss., TU Berlin, Berlin, 2003.
Bienstock, D., “Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and Practice”, International Series in Operations Research & Management Science, Springer, New York, USA, 2002.
Ben-Ameur, W., “Constrained-length connectivity and survivable networks”, Networks, 36 (1) (2000) 17–33.
Baier, G., Erlebach, T., Hall, A., Köhler, T., Kolman, P., Pangrác, O., Schilling, H., and Skutella, M., “Length-bounded cuts and flows”, ACM Trans. Algorithms, 7 (1) (2010) 4:1–4:27.
Castro, J., “Solving difficult multicommodity problems with a specialized interior-point algorithm”, Annals of Operations Research, 124 (2003) 35–48.
Castro, J., “Interior-point solver for convex separable block-angular problems”, Optimization Methods and Software, 31 (2016) 88-109.
Chaudhuri, K., Papadimitriou, C., and Rao, S., “Optimum routing with quality of service constraints”, Unpublished manuscript, 2004.
Dinic, E.A., “Algorithm for solution of a problem of maximum flow in networks with power estimation”, Soviet Mathematical Dokladi, 11 (1970) 1277–1280.
Fleischer, L.K., “Approximating fractional multicommodity flow independent of the number of commodities”, SIAM J. Disc. Math., 13 (2000) 505–520.
Frangioni, A., Gallo, G., “A bundle type dual-ascent approach to linear multicommodity min cost flow problems”, INFORMS Journal On Computing, 11 (1999) 370–393.
Garg, N. and Köemann, J., “Faster and simpler algorithms for multicommodity flow and other fractional packing problems”, in Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS’98), IEEE CS Press, Palo Alto, California, USA, 1998, 300–309.
Goldberg, A.V., Oldham, A.D., Plotkin, S., and Stein, C., “An implementation of an approximation algorithm for minimum-cost multicommodity flows”, in: Proceedings of the 6-th Integer Programming and Combinatorial Optimization, LNCS Vol. 1412, Berlin, Springer, 1998, 338–352.
Garg, N., Vazirani, V., and Yannakakis, M., “Primal-dual approximation algorithms for integral flow and multicut in trees”, Algorithmica, 18 (1997) 3–20.
Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., and Yannakakis, M., “Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems”, Proceedings of the 31st Annual ACM Symposium on Theory of Computing, ACM, Atlanta, GA, USA, 1999, 19–28.
Hu, T.C., Integer Programming and Network Flows, Addison-Wesley Publishing Company, Reading, MA, 1970.
Kleinberg, J.M., Approximation algorithms for disjoint paths problems, Ph.D. Diss., MIT, Cambridge, MA, 1996.
Kolliopoulos, S.G., Exact and approximation algorithms for network flow and disjoint-path problems, Ph.D. Diss., Dartmouth College, Hanover, NH, 1998.
Belaidouni, M. and Ben-Ameur, W., “On the minimum cost multiple-source unsplittable flow problem”, RAIRO Oper. Res. 41 (3) (2007) 253–273.
Kolman, P. and Scheideler, C., “Improved bounds for the unsplittable flow problem”, J. Algor., 61 (1) (2006) 20–44.
Malashenko, Yu.E. and Stanevichyus, I.A., “The solution of the multi-product problem with integer-valued flows”, USSR Computational Mathematics and Mathematical Physics, 22 (3) (1982) 245-249.
Nemhauser, G.L. and Wolsey, L.A., Integer and Combinatorial Optimization, Wiley-Interscience, New York, NY, 1988.
Van Mieghem, P., Kuipers, F.A., Korkmaz, T., Krunz, M., Curado, M., Monteiro, E., Masip-Bruin, X., Sole-Pareta, J., and Sanchez-Lopez, S., “Quality of service routing”, Quality of Future Internet Services, LNCS, Springer, Berlin, (2856) 2003, 80–117.
Radzik, T., “Experimental study of a solution method for multicommodity flow problems”, in Proceedings of the 2nd Workshop on Algorithm Engineering and Experiments, San Francisco, CA, USA, 2000, 79–102.
Schrijver, A., Combinatorial Optimization. Polyhedra and Efficiency, Vol. C, Springer, 2003.
Tang, Z., Zhao, B., Yu, W., Feng, Z., and Wu, C., “Software defined satellite networks: Benefits and challenges”, Proceedings of Computing, Communications and IT Applications Conference (ComComAp), IEEE, Beijing, China, 2014, 127-132.
Tardos, E., “A strongly polynomial algorithm to solve combinatorial linear programs”, Oper. Res., 34 (2) (1986) 250–256.
Tsaggouris, G. and Zaroliagis, C., “Multiobjective optimization: Improved FPTAS for shortest paths and non-linear objectives with applications”, Theory Comput. Syst., 45 (1) (2009) 162–186.
Villavicencio, J., “Solving multicommodity flow problems by an approximation scheme”, SIAM Journal on Optimization, 15 (4) (2005) 971–986.
Downloads
Published
Issue
Section
License
Copyright (c) 2019 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
