Some Complexity Results for the k-Splittable Flow Minimizing Congestion Problem

Chengwen Jiao, Qi Feng, Weichun Bu

College of Science, Zhongyuan University of Technology, Zhengzhou, China.

DOI: 10.4236/cn.2018.101001                

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.

Keywords

k-Splittable Flow, Minimize Congestion, Minimize Number of Rounds, Complexity

1. Introduction

In the traditional multi-commodity flow problems, flow being sent from the source nodes to the destination nodes may travel on large number of paths through the network. This effect is undesired or even forbidden in many applications. Such as in the modern broadband communication networks, namely the multiple protocol label-switched networks (MPLS), data packets are gathered under a single label with the aim to limit the routing tables and to increase the quality of data transmission. The label-switched paths (LSPs) must support the routing of data traffic between different terminal nodes, from one endpoint to another. An important feature of MPLS is its ability to set up traffic engineering mechanism (MPLS-TE). It can control the structure of the traffic for each customer by setting restriction on the number of routes the customer used. In order to preserve the QoS requirement, the demand of each customer must be satisfied. Using a single path would possibly increase the congestion of the network, while, on the other hand, a large number of LSPs would decrease the performance of the protocol, and the intermediate situation is considered in the MPLS network.

In 2002, Baier [1] proposed the k-splittable flow problem. Given a directed graph $G=\left(V,E,u,c\right)$ with arc capacities $u_e>0$ and arc cost $c_e>0,\forall e\in E$ . A set of commodities is denoted by $L$ , each commodity $l\in L$ has a certain amount of demand $d_l$ to transmit from a source node $s_l$ to a destination node $t_l$ . The number of paths each commodity can use is restricted, that is commodity $l$ can only use at most $k^l$ paths to transmit the flow. If each commodity uses exactly $k^l$ paths and the flow of each path is the same value, $d_l/k^l$ , this problem is called uniformed exactly k-splittable flow problem. If $k^l=1,\forall l\in L$ , this problem is in fact the unsplittable flow problem (UFP) which was introduced by Kleinberg [2] . If $k^l\ge \left|E\right|,\forall l\in L$ , it is in fact the traditional flow problem.

Kleinberg [2] introduced the following optimization versions of the unsplittable flow problem. Minimum congestion: find the smallest value $\alpha \ge 1$ such that there exists an unsplittable flow such that violates the capacity of any edge at most by a factor $\alpha$ . Minimum number of rounds: partition the set of commodities into a minimum number of subsets. Maximum routable demand: find a feasible unsplittable flow for a subset of demands maximizing the sum of demands in the subset. In this paper, we are mainly interested in the minimum congestion problem and minimum number of rounds problem.

For the unsplittable flow problem, Erlebach et al. [3] proved that for arbitrary $\epsilon$ , obtaining an approximation algorithm for minimizing congestion and cost with performance ratio better than $\left(2-\epsilon ,1\right)$ is NP-hard. The unsplittable flow problem is much easier if all commodities share a common single source node. However, the resulting single-source unsplittable flow problem still remains strongly NP-hard. Researches gave some approximation algorithms for this problem (see references [4] [5] [6] ).

As for the k-splittable flow problem, researchers generalize the above optimization versions and there are a lot of studies on the related problems. Baier et al. [7] solved the maximum Single- and Multi-commodity k-splittable flow problem using approximation algorithms. The authors proved that the maximum single- commodity k-splittable flow problem is NP-hard in the strong sense for directed graphs. Koch et al. [8] studied the single commodity maximum k-splittable flow problem. It is proved that when k is a constant, this problem is strongly NP-hard and obtaining an approximation algorithm with performance ratio better than $k/\left(k+1\right)$ is NP-hard. While when k is not a constant, obtaining an approximation algorithm with performance ratio better than 5/6 is NP-hard. Kolliopoulos [9] studied the approximation algorithms for the single source 2-splittable flow problem using rounding down strategy and Salazar et al. [10] considered the single source k-splittable flow problem using rounding up strategy. Truffot et al. [11] [12] [13] and Gamst et al. [14] [15] design branch-and-price exact algorithms for the k-splittable flow problem. Palel [16] used a randomized rounding approach to solve the k-splittable flow problem.

By the current researches, we can see that for the k-splittable flow problem, there is little research on the optimization version of minimizing congestion, especially for the complexity of this problem. In this paper, we give some complexity results for the minimizing congestion k-splittable flow problem. 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 2 is NP-hard. When k is an input, for the single commodity k-splittable flow problem, obtaining an algorithm with performance ratio better than $\left(\sqrt{5}+1\right)/2$ is NP-hard. We also study the relationship between minimum congestion and minimum number of rounds.

2. Some Complexity Results

In this section, we will give three complexity results for the minimizing congestion k-splittable flow problem. These results are given by the following Theorems.

Theorem 1: For the k-splittable multi-commodity transmission problem, the existence of a feasible solution is strongly NP-hard.

Proof: Given an instance of the 3-partition problem with 3n elements, $a_i,1\le i\le 3n$ . ${\displaystyle {\sum }_{i=1}^{3n}{a}_i}=n\cdot d$ . For arbitrary i, we suppose that $d/4<a_i<d/2$ . Next construct a simple directed graph G, see Figure 1. The network has 2 nodes, one is source node s, and the other is sink node t. There are 3n parallel directed edges from s to t with edge capacities $a_i,1\le i\le 3n$ , respectively. n commodities from s to t with same demands d need to be transmitted. Each commodity can use at most 3 paths.

If the 3-partition has a solution, that is, the 3n elements can be partitioned into n sets. Each set has 3 elements and the total value of the 3 elements is exactly d. For each commodity, it can use the 3 edges corresponding to one of the n sets to transmit flow. The demands of the n commodities can be transmitted through the 3n edges of G. Thus there is a 3-splittable flow with congestion 1 to satisfy the demands of the n commodities in the network. On the other hand, if there is a feasible 3-splittable flow satisfying the demands in the network, since each edge

Figure 1. Network G obtained by 3-partition instance.

capacity is less than d/2 and larger than d/4 and the number of paths each commodity can use is at most 3, we have that each commodity must use exactly 3 paths to transmit the demand and the total flow value of the paths is d. In this way, we obtain a feasible solution of the 3-partition instance. Partite the 3n elements into n sets, the elements in each set corresponding to the transmitting paths of some commodity and the total value of the 3 elements are exactly d.

Since the 3-partition problem is strongly NP-hard, by the above discussion, we know that the existence of a feasible solution of the k-splittable flow problem is also strongly NP-hard. ,

For the uniformly exactly k-splittable flow problem, by referring the construction strategy used in [2] to prove some complexity result of the unsplittable flow problem, we can obtain the following theorem.

Theorem 2: When the number of the source nodes N is an input, for the uniformly exactly k-splittable flow minimizing congestion problem, obtaining an approximation algorithm with performance ratio better than 2 is NP-hard.

Proof: Given an instance of a 3-D matching. Denote set $A=\left\{a_1,a_2,\cdots ,a_n\right\}$ , set $B=\left\{b_1,b_2,\cdots ,b_n\right\}$ , set $C=\left\{c_1,c_2,\cdots ,c_n\right\}$ . A set $I\subseteq A\times B\times C$ is given with $\left|I\right|=m$ . Suppose that all the 3n elements in $A,B,C$ appear in I. Further, if there is a subset $M\subseteq I$ with $\left|M\right|=n$ and all the elements in $A,B,C$ appear in M, that is each element in $A,B,C$ appears exactly one time in M, we say that there is a 3-D matching in I, and so the 3-D matching instance has a solution. Next we construct a directed graph G and an instance $I^{\prime }$ of the k-splittable flow problem. There are N source nodes in G, namely $S_1,S_2,\cdots ,S_N$ . Suppose $a_i\in A,i=1,\cdots ,n$ , appears $t_i$ times in I, that is there are $t_i$ triples contains $a_i$ in I.

For each $u=\left(a_i,b_j,c_h\right)$ , there is only one node in G corresponding to $b_j$ and there are $N-1$ nodes in G corresponding to $c_h$ , denote them by $c_h^1,c_h^2,\cdots ,c_h^{N-1}$ . For $a_i$ , there are $t_i-1$ sink nodes $T_i^1,T_i^2,\cdots ,T_i^{t_i-1}$ and $\left(N-1\right)\left(t_i-1\right)$ virtual nodes in G. For $u=\left(a_i,b_j,c_h\right)$ , there are two nodes $x_u,y_u$ in G. The construction of the subgraph of G corresponding to u is showed in Figure 2.

There are directed edges $\left(S_1,b_j\right),\left(S_2,b_j\right),\cdots ,\left(S_{N-1},b_j\right)$ , $\left(b_j,x_u\right)$ , $\left(x_u,y_u\right)$ , $\left(S_N,x_u\right)$ , $\left(y_u,c_h^1\right),\left(y_u,c_h^2\right),\cdots ,\left(y_u,c_h^{N-1}\right)$ in G. For $r=1,2,\cdots ,t_i-1$ , there are $N-1$ edge-disjoint paths going through the virtual nodes from $y_u$ to the sink node $T_i^r$ , respectively. The edge capacities of $\left(b_j,x_u\right),\left(x_u,y_u\right),\left(S_N,x_u\right)$ are all $N-1$ and the capacities of the remaining edges are 1. There are two classes of commodities, one is called C-class commodity, the other is called T-class commodity. The C -class commodity is from $S_p$ to $c_h^p$ with demand 1, $h=1,\cdots ,n$ , $p=1,\cdots ,N-1$ . Each C-class commodity can only use one path to transmit flow. The T-class commodity is from $S_N$ to $T_i^r$ with demand $N-1$ , $i=1,\cdots ,n$ , $r=1,\cdots ,t_i-1$ . Each T-class commodity can use $N-1$ paths to transmit flow.

If there is a 3-D matching in I, we can prove that there exists a uniformly exactly k-splittable flow in G that satisfying the demands of all commodities with

Figure 2. The subgraph of G corresponding to triple $u=\left(a_i,b_j,c_h\right).$

congestion value 1. Suppose the 3-D matching in I is M. For each triple $\left(a_i,b_j,c_h\right)$ in M, there is a path from $S_p$ to $c_h^p$ with flow 1, $p=1,\cdots ,N-1$ . That is the C-class commodity can be satisfied by the subgraphs corresponding the triples in M. For the T-class commodity, they can be satisfied by the subgraphs corresponding to the triples in $I\backslash M$ . Since $a_i$ appears $t_i$ times in I, while in M, it appears exactly once, the remaining $t_i-1$ times appears in $I\backslash M$ , for $r=1,\cdots ,t_i-1$ , there are $N-1$ paths from $S_N$ to $T_i^r$ with flow 1.

If there is a uniformly exactly k-splittable flow in G satisfying all commodities, there is a 3-D matching in I. Suppose the triples that satisfying the C-class commodity be M, we will prove that M is in fact a 3-D matching in I. The number of T-class commodity is ${\displaystyle {\sum }_{i=1}^n\left(t_i-1\right)}=m-n$ and each T-class commodity needs $N-1$ paths with flow 1 from source node $S_N$ to sink node $T_i^r$ . Each transmitting path of both C-class commodity and T-class commodity contains exactly one edge of kind of $\left(x_u,y_u\right)$ . Since the number of this kind of edges is m and the capacities of these edges are $N-1$ , the C-class commodity can only use $m-\left(m-n\right)=n$ − $\left(x_u,y_u\right)$ class edge which corresponding to n triples, that is M. For $p=1,\cdots ,N-1$ , the commodity from $S_p$ to $c_h^p$ can only use one triple containing $a_i$ (the remaining $t_i-1$ triples containing $a_i$ are used by T-class commodity), that is all the elements in A appear in M. Since the total number of incoming edges with capacity 1 of $b_j$ is $N-1$ and the total demands of the C-class commodity which must going through the nodes corresponding to elements in set B are $\left(N-1\right)n$ , the triples in M contains all the elements in B. Furthermore, since the number of triples in M is n, there is only one triple contains $b_j,j=1,\cdots ,n$ . Since the demand of the sink node $c_h^p$ is 1 and all the demands of the C-class commodity are satisfied, the triples in M must contain all the elements in C. Similarly, since the number of triples in M is n, there is exactly one triple in M containing $c_h,h=1,\cdots ,n$ . By the above discussion, we prove that M is indeed a 3-D matching of I.

Since the maximum flow from the source node to the sink node in G is 1, if there is no 3-D matching, it is easy to see that there is no uniformly exactly k-splittable flow in G that satisfying the capacity constraints. When $N=2$ , the capacity value of all the edges in G is 1. When there is no 3-D matching in I, the congestion values of G is at least 2. Since the 3-D matching problem is a NP-hard problem, for the uniformly exactly k-splittable flow problem, obtaining an approximation algorithm with congestion value less than 2 is NP-hard. ,

Theorem 3: When k is an input, for the single commodity k-splittable flow minimizing congestion problem, obtaining an approximate algorithm with performance ratio better than $\delta$ is NP-hard, in which $\delta =\left(\sqrt{5}+1\right)/2$ .

Proof: We prove this theorem by SAT reduction, referring the construction strategy used in Baier [1] to prove some NP-hard problem. Given an instance of SAT, the variable set is $\left\{x_1,x_2,\cdots ,x_n\right\}$ and there are m subsets of $\left\{x_1,\cdots ,x_n,{}^{\neg }x{}_1,\cdots ,{}^{\neg }x{}_n\right\}$ , namely $C_1,\cdots ,C_m$ . Next we construct a directed graph G, see Figure 3, the demand of the single commodity from source node s to sink node t is $k-1+\delta$ . Next we will prove that if there is a feasible solution of the SAT problem, that is there existing a 0-1 assignment to $x_1,\cdots ,x_n$ such that each subset $C_j,j=1,\cdots ,m$ , containing at least one element with value 1, the congestion value of G is 1. Otherwise, if there is no feasible solution of the SAT problem, the congestion value of G is at least $\delta$ .

There are three steps to construct the directed graph G. Step 1, construct n-parallel chains connected by $n+1$ directed edges. The n parallel chains correspond to variables $x_i,i=1,\cdots ,n$ , respectively. For each parallel chain, denote one of it by true chain, the other by false chain. The number of edges in each chain is equal to $4n+2$ . The capacities of all the current constructed edges are $\delta$ . Step 2, we continue to construct edges for G using the m subsets $C_1,\cdots ,C_m$ . For each $j=1,\cdots ,m$ , there are two nodes, namely $u_j,v_j$ , in G corresponding to subset $C_j$ . The new directed edges are $\left(s,u_1\right),\left(v_j,u_{j+1}\right),j=1,\cdots ,m-1$ and $\left(v_m,t\right)$ . For each subset $C_j$ , if ${}^{\neg }x{}_i\in C_j$ , two adjacent edges in the true chain of $x_i$ are corresponding to $C_j$ only. Two new directed edges are constructed: $u_j$ is connected to the first node of the first edge and the second node of the

Figure 3. The graph G constructed by an instance of the SAT problem.

first edge is connected to $v_j$ . Similarly, if $x_i\in C_j$ , two adjacent edges in the false chain of $x_i$ are corresponding to $C_j$ only. Two new directed edges are constructed: $u_j$ is connected to the first node of the first edge and the second node of the first edge is connected to $v_j$ . Since each chain contains $4n+2$ directed edges and the number of elements in each subset $C_j$ is at most 2n, Step 2 can be implemented successfully. If there are more than one subsets contain the same variable, these adjacent edges corresponding to each subset are arranged by the decreasing order of the subset index. Step 3, add $k-2$ directed edges from s to t. The capacities of all the new constructed edges in Step 2 and Step 3 are equal to 1 (see Figure 3).

If there is a feasible solution of the SAT problem, that is there existing a 0 - 1 assignment to $x_1,\cdots ,x_n$ such that each subset $C_j,j=1,\cdots ,m$ , contains at least one element with value 1. By the construction of Step 2, we know that there are two adjacent edges corresponding to this 1-value element, denote the first edge by the key edge of $C_j$ . From s, followed by $u_j$ , the key edge of $C_j$ , and node $v_j,j=1,\cdots ,m$ , we can obtain a $s\text{-}t$ path with flow value 1, denote this path by $P_1$ . From s, followed by the chains not used by $P_1$ , we can obtain another $s\text{-}t$ path with flow value $\delta$ . Together with the $k-2$ edges from s to t, we obtain $ks\text{-}t$ paths with flow value $k-1+\delta$ and the congestion of G is 1. If there is a k-splittable flow satisfying the demand with congestion value 1, there is a feasible solution of the SAT problem. Since the total capacity of the directed edges going out from s is $k-1+\delta$ and the maximum capacity of the $s\text{-}t$ paths is $\delta$ , furthermore, the commodity can use at most k paths, according the above reasons, we know that there must be $k-1s\text{-}t$ paths with flow 1 and one $s\text{-}t$ path with flow $\delta$ . Denote P be the path from s followed by $u_1$ . Assign the variables corresponding to the chains that path P transformed to 1. Since the congestion is 1, P and the path with flow $\delta$ must be edge-disjoint. Then the path P must go through $u_1,v_1,\cdots ,u_m,v_m$ and the key edges of $C_1,\cdots ,C_m$ . And so for each $C_j,j=1,\cdots ,m$ , there must be an element with value 1, and a feasible solution of the SAT is obtained.

Now suppose there is no feasible solution of the SAT problem, the paths from s with length larger than 1 must not be edge-disjoint (otherwise, it contradicts to the hypothesis), the congestion of any k-splittable flow satisfying the demand is at least $\left(\delta +1\right)/\delta$ or $\delta$ . Since the SAT problem is NP-hard, for the k-splittable single commodity problem with k as an input, obtaining an approximation algorithm with congestion less than $\delta$ is NP-hard. ,

3. Minimum Number of Rounds

In this section, we consider the minimum number of rounds of the k-splittable flow problem. The demand $d_l$ of commodity $l$ can be transformed in multiple times and the total number of the transmission paths cannot be larger than $k^l$ . The objective of this problem is to transform all commodities but using least times of the network. Minimizing number of rounds reduce the total transmission cost in some extent. In the k-splittable flow problem, there is some relationship between minimum congestion and minimum number of rounds and we have the following Theorem.

Theorem 4: Given a network G and a commodity set L, the commodities in L share a common source node s. Suppose $d_{\max }\le u_{\min }$ . If for arbitrary feasible flow x that satisfies all the demands $d_1,d_2,\cdots ,d_{\left|L\right|}$ , there exists a k-splittable flow y that satisfies the demands and the path restrictions, and for arbitrary $e\in E$ , $y_e\le \alpha \cdot u_e$ , we have that for all the commodities with demand not larger $u_{\min }/q$ can be transformed in $\lceil \alpha \rceil$ rounds, in which $q\ge \lceil \alpha \rceil$ .

Proof: Copy the network G in $\lceil \alpha \rceil$ times, denoting them by $G_1,\cdots ,G_{\lceil \alpha \rceil }$ , respectively. For each $e\in E\left(G\right)$ , its capacity in $G_j,j=1,\cdots ,\lceil \alpha \rceil$ is defined by $u_e/\lceil \alpha \rceil$ . Adding a super source node S and $\left|L\right|$ super sink nodes $T_1,\cdots ,T_{\left|L\right|}$ . For each $j=1,\cdots ,\lceil \alpha \rceil$ , connect the super source node S to the source node s in $G_j$ , the sink nodes $t_i$ is connected to $T_i,i=1,\cdots ,\left|L\right|$ . The capacities of all the new edges are $+\infty$ . The construction of the new network is showed in Figure 4, denote it by $G^{\prime }$ . In $G^{\prime }$ , there are $\left|L\right|$ commodities with demand $d_i$ and path restriction number $k^i$ from source node S to the sink node $T_i,i=1,\cdots ,\left|L\right|$ , respectively. Denote the commodity set in $G^{\prime }$ by $L^{\prime }$ . Suppose x is a feasible flow in G satisfying all the commodities in L. By the construction of $G^{\prime }$ , we can obtain a feasible flow $x^{\prime }$ from x in $G^{\prime }$ satisfying all the commodities in $L^{\prime }$ . For $j=1,\cdots ,\lceil \alpha \rceil$ , the flow value $x^{\prime }\left(e\right)$ of edge $e\in E\left(G^{\prime }\right)$ is $x_e/\lceil \alpha \rceil$ . Denote the set $L^{*}$ be the commodities in $G^{\prime }$ with demands not larger than $u_{\min }/q$ . It is easily to see that we can obtain a feasible flow $x^{*}$ from $x^{\prime }$ satisfying $L^{*}$ . Since $u_{\min }/q$ is not larger than the minimum capacity $u_{\min }/\lceil \alpha \rceil$ of $G^{\prime }$ , by the theorem hypothesis, there is a k-splittable flow y in $G^{\prime }$ satisfying the demands and path restrictions of commodities in $L^{*}$ . Further, for any $j=1,\cdots ,\lceil \alpha \rceil$ , $e\in E\left(G_j\right)$ , we have that

$y\left(e\right)\le \alpha \cdot x^{*}\left(e\right)\le \alpha \cdot x^{\prime }\left(e\right)=\alpha \cdot \frac{x\left(e\right)}{\lceil \alpha \rceil }\le x\left(e\right)\le u(e)$

That is in y, the flow value of each edge in $G_j$ is not larger than the capacity of the original graph G. Since in flow y, the paths from S to $T_i$ can be transformed

Figure 4. The construction of G'.

into paths from s to $t_i$ in G, and the number of paths is not larger than $k^i$ , and then the commodities in L with demands not larger than $u_{\min }/q$ can be transformed into $\lceil \alpha \rceil$ rounds. The transmission paths and their path values in round j are corresponding to the transmission paths with their flow values in y in $G_j,j=1,\cdots ,\lceil \alpha \rceil$ . ,

In inference [10] , for the minimizing congestion k-splittable flow problem, there is a theorem as follows.

Theorem 5 [10] : For the single source k-splittable flow problem, suppose the number of paths each commodity can use is all equal to k. For any feasible flow x that satisfying all the demands $d_1,\cdots ,d_{\left|L\right|}$ , there exists a k-splittable flow y that satisfies the demands and the path restrictions, and for arbitrary $e\in E,$

$y\left(e\right)\le \frac{2k}{2k-1}x\left(e\right)+\frac{d_{\max }}{k}$ .

In Theorem 5, it is not required that $d_{\max }\le u_{\min }$ , similar to the proof in Theorem 4, we can have that for the commodities with demands between in $\left(0,q\cdot u_{\min }\right]$ , if we require these commodities be transmitted in r rounds, as long as the following inequality holds:

$\frac{2k}{2k-1}\cdot \frac{1}{r}+\frac{1}{k}\cdot q\le 1$

By the above inequality, we know that when $k=2$ , all the commodities with demands not larger than $\frac{2}{3}\cdot u_{\min }$ can be transmitted in 2 rounds. For the general $k\ge 2$ , all the commodities with demands not larger than $u_{\min }$ can be transmitted in 3 rounds.

4. Conclusion

In this paper, we give some complexity results of minimizing congestion in the k-splittable flow problem. The two approximation algorithms in [9] and [10] are all relied on the unsplittable flow algorithms. In the future, we will design approximation algorithms for minimizing congestion of the k-splittable flow problem using new strategies.

Acknowledgements

The work is supported by the National Natural Science Foundation of China under Grant No.11701595.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Baier, G. (2003) Flows with Path Restrictions. Ph.D. Thesis, Technische Universitat Berlin, Berlin.
[2]	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
[3]	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.
[4]	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
[5]	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
[6]	Skutella, M. (2002) Approximating the Single-Source Unsplittable Min-Cost Flow Problem. Mathematical Programming, 91, 493-514. https://doi.org/10.1007/s101070100260
[7]	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
[8]	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.
[9]	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
[10]	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
[11]	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
[12]	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.
[13]	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
[14]	Gamst, M., Jensen, P.N., Pisinger, D. and Plum, C. (2010) Two- and Three-Index Formulations of the Minimum Cost Multicommodity k-Splittable Flow Problem. European Journal of Operational Research, 202, 82-89. https://doi.org/10.1016/j.ejor.2009.05.014
[15]	Gamst, M. and Petersen, B. (2012) Comparing Branch-and-Price Algorithms for the Multicommodity k-Splittable Maximum Flow Problem. European Journal of Operational Research, 217, 278-286. https://doi.org/10.1016/j.ejor.2011.10.001
[16]	Pawel, M.B. (2017) A Randomized Rounding Approach to a k-Splittable Multicommodity Flow Problem with Lower Path Flow Bounds Affording Solution Quality Guarantees. Telecommunication Systems, 64, 525-542. https://doi.org/10.1007/s11235-016-0190-2