VPN costs on the edges

The vectors b+and b−specify a set of valid traffic matrices that can beinterpreted as follows. Let KS,R be the complete bipartite graph with nodespartitioned into senders and receivers: each valid traffic matrix corresponds to afractional b-matching on KS,R and vice versa.A solution to an instance of the problem is a pair (P, x), where P is acollection of paths P := {Psr | ∀r ∈ R, s ∈ S}, and x ∈ QE+ specifies the capacityto install on each edge of the network. A solution is feasible if the installedcapacities suffice to route each valid traffic matrix via the selected paths P. Afeasible solution is optimal if it minimizes the emerging costPe∈Ece  f(xe).If f(xe) = xe, that means we have linear costs on the edges, we term thisproblem just Virtual Private Network (Vpn) problem. We call an instance ofthe problem balanced whenever S :=Ps∈Sb+sequals R :=Pr∈R b−r.Given a collection of paths P, the minimum amount of capacity xe that hasto be install on e ∈ E to turn (P, x) into a feasible solution can be computed inpolynomial time as follows (see [2,5,4] for details):xe = maximal cardinality of a b-matching in Ge = (S ∪ R, Ee),with (s, r) ∈ Ee ⇔ e ∈ PsrNotice that, since the graph Ge is bipartite, an optimum capacity reservationvector x will always be integer.Single Sink Buy-At-Bulk. An instance of the Single Sink Buy-At-Bulk (Ssbb)problem consists of an undirected connected graph G = (V, E) with edge costsc : E → Q+, a demand function d : V → N, a root r ∈ V and a concavenon-decreasing function f : Q+ → Q+.The aim is to find capacities xe ∈ Q+ for the edges, sufficient to simultaneously route a demand of d(v) from each node v to the root, such that theemerging costPe∈Ece  f(xe) is minimized.Sometimes it is assumed that d(v) ∈ {0, 1}, and in this case the verticesD = {v ∈ V | d(v) = 1} are called clients