Sink Buy-At-Bulk (Ssbb) problem VPN

Recently, Fiorini et al. [10] started the investigation of the symmetric Vpnproblem with concave costs. More precisely, the concave symmetric Vpn problemis defined as the symmetric Vpn problem, but the contribution of each edge to the total cost is proportional to some concave non-decreasing function of thecapacity reservation. The motivation for studying this problem is due to thefact that buying capacity can often reflect an economy of scale principle: themore capacity is installed, the less is the per-unit reservation cost. They givea constant factor approximation algorithm for the problem, and show that alsoin this case there always exists an optimal solution that has a tree structure.An alternative subsequent proof of the latter result is also given by Goyal et al.[13]. The investigation of the concave asymmetric Vpn problem has not beenaddressed so far.The importance of tree solutions becomes more evident in the context ofsymmetric Vpn and balanced Vpn, where any tree solution has in fact a centralhub node, as shown by [2] for the symmetric case and by [5] for the balancedcase. More precisely, any tree solution in these cases has enough capacity suchthat all the terminal nodes could simultaneously route their traffic to some hubnode r in network. Combining this with some simple observations, it followsthat computing the cheapest tree solution reduces to computing the cheapestway to simultaneously send a given amount flow from the terminal nodes tosome selected hub node r. In case of linear edge costs [2,5], the latter min-costflow problem becomes simply a shortest path tree problem. In case that the edgecosts are proportional to a non-decreasing concave cost function [10], the lattermin-cost flow problem is known as Single Sink Buy-At-Bulk (Ssbb) problem (aformal definition is given in the next section). Differently, the above propertydoes not hold for tree solutions of asymmetric Vpn instances.