Point-to-multipoint minimum cost flow problem with convex cost function

In this paper, we introduce a point-to-multipoint minimum cost flow problem with convex cost and demand splitting. A source node transmits the traffic along the tree that includes members of the point-to-multipoint connection. The traffic is replicated by the nodes only at branch points of the tree. In order to minimize the sum of arc costs, we assume that the traffic demand can be split and transmitted to destination nodes along different trees. If arc cost is linear, the problem would be a Steiner tree problem in networks even though demand splitting is permitted. The problem would be applied in transmitting large volume of traffic from a server to clients in Internet environments. Optimality conditions of the problem are presented in terms of fair tree routing. The proposed algorithm is a finite terminating algorithm for ϵ-optimal solution. Convergence of the algorithm is obtained under monotonic condition and strict convexity of the cost function. Computational experiences are included.