Research ArticleOpen AccessGoogle Scholar indexed
Some Complexity Results for the k-Splittable Flow Minimizing Congestion Problem
College of Science, Zhongyuan University of Technology, Zhengzhou, China
College of Science, Zhongyuan University of Technology, Zhengzhou, China
College of Science, Zhongyuan University of Technology, Zhengzhou, China
- 1 College of Science, Zhongyuan University of Technology, Zhengzhou, China
- 2 College of Science, Zhongyuan University of Technology, Zhengzhou, China
- 3 College of Science, Zhongyuan University of Technology, Zhengzhou, China
Communications and Network·Volume 10 (2017)·Pages 1–10·Published 13 December 2017·DOI10.4236/cn.2018.101001
Copy link · social · email
Abstract
In this paper, we mainly consider the complexity of the k-splittable flow minimizing congestion problem. We give some complexity results. For the k-splittable flow problem, the existence of a feasible solution is strongly NP-hard. When the number of the source nodes is an input, for the uniformly exactly k-splittable flow problem, obtaining an approximation algorithm with performance ratio better than ( √5+1 )/2 is NP-hard. When k is an input, for single commodity k-splittable flow problem, obtaining an algorithm with performance ratio better than is NP-hard. In the last of the paper, we study the relationship of minimizing congestion and minimizing number of rounds in the k-splittable flow problem. The smaller the congestion is, the smaller the number of rounds.
Keywordsk-Splittable FlowMinimize CongestionMinimize Number of RoundsComplexity
- Baier, G. (2003) Flows with Path Restrictions. Ph.D. Thesis, Technische Universitat Berlin, Berlin.
- Kleinberg, J. (1996) Single-Source Unsplittable Flow. Proceedings of the 37th Annual Symposium on Foundations of Computer Science, Burlington, 14-16 October 1996, 68-77. https://doi.org/10.1109/SFCS.1996.548465
- Erlebach, T. and Hall, A. (2002) NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow. Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 6-8 January 2002.
- Dinitiz, Y., Garg, N. and Goemans, M.X. (1999) On the Single Source Unsplittable Flow Problem. Combinatorica, 19, 1-25. https://doi.org/10.1007/s004930050043
- Kolliopoulos, S.G. and Stein, C. (2001) Approximation Algorithms for Single-Source Unsplittable Flow. SIAM Journal on Computing, 31, 919-946. https://doi.org/10.1137/S0097539799355314
- Skutella, M. (2002) Approximating the Single-Source Unsplittable Min-Cost Flow Problem. Mathematical Programming, 91, 493-514. https://doi.org/10.1007/s101070100260
- Baier, G., Kohler, E. and Skutella, M. (2005) On the k-Splittable Flow Problem. Algorithmica, 42, 231-248. https://doi.org/10.1007/s00453-005-1167-9
- Koch, R., Skutella, M. and Spenke, I. (2005) Approximation and Complexity of k-Splittable Flows. In: Erlebach, T. and Persinao, G., Eds., Approximation and Online Algorithms, WAOA 2005, Springer, Berlin, 244-257.
- Kolliopoulos, S.G. (2005) Minimum-Cost Single-Source 2-Splittable Flow. Information Processing Letters, 94, 15-18. https://doi.org/10.1016/j.ipl.2004.12.009
- Salazar, F. and Skutella, M. (2006) Single-Source k-Splittable Min-Cost Flows. Operations Research Letters, 37, 71-74. https://doi.org/10.1016/j.orl.2008.12.004
- Truffot, J. and Duhamel, C. (2008) A Branch and Price Algorithm for the k-Splittable Maximum Flow Problem. Discrete Optimization, 5, 629-646. https://doi.org/10.1016/j.disopt.2008.01.002
- Truffot, J., Duhamel, C. and Mahey, P. (2005) Using Branch-and-Price to Solve Multicommodity k-Splittable Flow Problem. Proceedings of International Network Optimization Conference (INOC), Lisbonne, 20-23 March 2005.
- Truffot, J., Duhamel, C. and Mahey, P. (2007) k-Splittable Delay Constrained Routing Problem: A Branch and Price Approach. 6th International Workshop on Design and Reliable Communication Networks (DRCN), La Rochelle, 7-10 October 2007. https://doi.org/10.1109/DRCN.2007.4762284