An approximation algorithm for minimizing congestion in the single-source k-splittable flow


An approximation algorithm for minimizing congestion in the single-source k-splittable flow


Chengwen Jiao*, Qi Feng, Weichun Bu

College of Science, Zhongyuan University of Technology, Zhengzhou, Henan 450007, People’s Republic of China


Research Journal of Mathematics and Computer Science

In the traditional multi-commodity transmission networks, the number of paths each commodity can use is unrestricted, and the commodities can use arbitrary number of paths to transmit the flow. However, in the real transmission networks, too many paths will increase the total transmission cost of the network and also cause difficulties in the management of the network. In 2002, Baier[1] proposed the-splittable flow problem, in which each commodity can only use a limited number of paths to transmit the flow. In this paper, we study the-splittable multi-commodity transmission flow problem with the objective of minimizing congestion and cost. We propose an approximation algorithm with performance ratio  for congestion and cost in the single-source case, in which is the minimum value of the number of paths each commodity can use. The congestion reflects the total load of the network to some extent. The main aim of minimizing congestion is to distribute the demands of the commodities on the network in a balanced way, avoiding the case that some edge is used too much. By this way, the performance of the network as a whole can be guaranteed and more commodities can be served.


Keywords: k-splittable flow, congestion minimization, approximation algorithm

Free Full-text PDF


How to cite this article:
Chengwen Jiao et al., An approximation algorithm for minimizing congestion in the single-source k-splittable flow. Research Journal of Mathematics and Computer Science, 2017; 1:8.


References:

[1] G.Baier. Flows with path restrictions. Ph.D. Thesis, Technisce Universitat Berlin, Cuvillier Verlag Gottingen, 2003.
[2] J.Kleinberg. Single-source unsplittable flow. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996, pp.68-77.
[3] T.Erlebach, A.Hall. NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow. In: Proc.13th ACM-SIAM Symp, On discrete Algorithms, 2002.
[4] Y.Dinitiz, N.Garg, M.X.Goemans. On the single source unsplittable flow problem. Combinatorica 19, 1-25, 1999.
[5] S.G.Kolliopoulos and C.Stein. Approximation algorithms for single-source unsplittable flow. SIAM Journal on Computing, 31(3): 919-946, 2001.
[6] M.Skutella. Approximating the single-source unsplittable min-cost flow problem. Mathematical Programming, 91, 493-514, 2002.
[7] G.Baier, E.Kohler, and M.Skutella. On the k-splittable flow problem. Algorithmica, 42: 231-248, 2005.
[8] R.Koch., M.Skutella, and I.Spenke. Approximation and complexity of k-splittable flows. In: Approximation and Online Algorithms, Third International Workshop, WAOA, 244-257, 2005.
[9] R.Koch., M.Skutella, and I.Spenke. Maximum k-splittable s,t-flows. Theory of Computing Systems, 43(1): 56-66, 2006.
[10] S.G.Kolliopoulos. Minimum-cost single-source 2-splittable flow. Information Processing Letters, 94(1): 15-18, 2005.
[11] F.Salazar and M.Skutella. Single-source k-splittable min-cost flows. Operations research letters, 37:71-74,2006.
[12] M.Martens, F.Salazar, and M.Skutella.Representing single source multi-commodity flows as convex combinations of unsplittable flows. L.Arge, M.Hoffmann, E.Welzl(Eds), Algorithms-ESA 2007, Lecture Notes in Computer Sciences, Vol.4698, Springer, Berlin, 395-406, 2007.