spanning the terminals VPN

Single Sink Rent-or-Buy. An instance of the Single Sink Rent-or-Buy (Srob)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 parameterM ≥ 1.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  min{xe, M} is minimized. Note that this problem is aspecial case of Single Sink Buy-At-Bulk.Steiner Tree. An instance of the Steiner tree problem consists of an undirectedconnected graph G = (V, E) with edge costs c : E → Q+ and a set of terminalsK ⊆ V .The aim is to find the cheapest tree T ⊆ E spanning the terminals. We now state the first constant factor approximation algorithm for cVpn, starting with some simplifying assumptions that we can make on a cVpn instancewithout loss of generality.First, by duplicating nodes, we may assume b+, b−to be 0/1 vectors, thatmeans, b+s = 1, b−s = 0 for a sender s, and b+r = 0, b−r = 1 for a receiver r. Thelatter assumption is correct if we can guarantee that the paths in a solutionbetween copies of a terminal v and copies of a terminal u are all the same. Ouralgorithm developed below can be easily adapted in such a way that it satisfiesthe latter consistence property, and that it runs in polynomial time even if thethresholds are not polynomially bounded. Note that, under these assumptions,S = |S| and R = |R|. Then by symmetry, suppose that |R| ≥ |S|.We propose the following algorithm Note that f(min{xe, |S|}) indeed is concave and non-decreasing in xe. LetOP T := OP TVpn(I) be the optimum cost for the cVpn instance I.Let us first argue, that the capacity reservation x′ein fact suffices. Consideran edge e, which is used by k paths in the Ssbb solution. Then the capacityreservation is x′e ≥ min{k, |S|}. It is easy to see that this is sufficient for theconstructed cVpn solution. Clearly the cost of this solution is equal to the costof the Ssbb-solution.We will now show that indeed, there is a Ssbb-solution of cost at most 2OP Tfor the instance defined in Step (2) of the algorithm. As it was pointed out in[10], any solution for Ssbb can then be turned into a tree solution of at mostthe same cost1.To prove this, we first define I′as a modified cVpn instance, which differsfrom I in such a way that there is a single sender with non-unit threshold, andin particular Intuitively we reroute all flow through the hub s∗. We will now prove that thisnew cVpn instance coincides with the Ssbb problem, i.e. their optimum valuesare identical.Let OP TSsbb be the cost of an optimum Ssbb solution for the instance definedin Step (2) of the algorithm.Lemma 1. OP TVpn(I′) = OP TSsbb.Proof. Let Ps∗v be the paths in a cVpn solution for I′. Consider an edge e ∈ Eand let v1, . . . , vk ∈ S ∪ R be the nodes, such that e ∈ Ps∗ vi. If k ≤ |S| we candefine a traffic matrix in which s∗sends 1 unit of flow to all vi. If k > |S|, wemay send 1 unit of flow from s∗to each node in v1, . . . , v|S|. Anyway the neededcapacity of e is xe = min{k, |S|}, which costs ce  f(min{k, |S|}). This is thesame amount, which an Ssbb solution pays for capacity k on e ∈ E. Thus bothproblems are equal. ⊓⊔The critical point is to show that:Lemma 2. E[OP TVpn(I′)] ≤ 2  OP TVpn(I).Proof. Let P = {Psr | s ∈ S, r ∈ R} be the set of paths in the optimum cVpnsolution for I and xe be the induced capacities. We need to construct a cVpnsolution of I′, consisting of s∗-v paths P′s∗ vfor v ∈ S ∪ R.The solution is surprisingly simple: Choose a receiver r∗∈ R uniformly atrandom as a second hub. Take P′s∗r:= Ps∗r as s∗-r path. Furthermore concatenate P′s∗s:= Ps∗r∗ + Pr∗s to obtain a s∗-s path. To be more precise we canshortcut the latter paths, such that they do not contain any edge twice.We define a sufficient capacity reservation x′eas follows: Install |S| units ofcapacity on the path Ps∗r∗ . Then for each sender s ∈ S (receiver r ∈ R) install ina cumulative manner one unit of capacity on Psr∗ (on Ps∗r , respectively). Notethat x′eis a random variable, depending on the choice of s∗and r∗. We showthat E[x′e] ≤ 2xe. Once we have done this, the claim easily follows from Jensen'sinequality and concavity of f:E[OP TVpn(I′)] ≤ E[Xe∈Ecef(x′e)] ≤Xe∈Ecef(E[x′e])] ≤ 2  OP TVpn(I)