VPN computed in polynomial time

We give the first constant factor approximation algorithm for the asymmetricVpn problem with arbitrary concave costs, showing that a tree solution of expected cost at most 49.84 OP T can be computed in polynomial time. Moreover,in case of linear cost, we show that for any fixed ε > 0 a (2 + εRS)-approximate solution can be obtained in polynomial time, with R :=Pvb−v, S :=Pvb+v,and without loss of generality R ≥ S.The key-point of our approximation results is showing that there always exists a cheap solution with a capacitated central hub node, which in particular hasa cost of at most twice the optimum. More precisely, there exists a 2-approximatesolution with enough capacity such that any subset of terminals could simultaneously send their flow to a hub node r up to a cumulative amount of S. Then,we show how to approximate such a centralized solution by using known resultson Ssbb. Based on this, we can then state that there exists a Vpn tree solution,with cost at most 2  OP T . This substantially improves the previous known upper bound of 4.74 on the ratio between an optimal solution and an optimal treesolution, which only applies in case of linear costs. We remark that our resultholds considering any non-decreasing concave cost function.The technique used to prove our results is substantially different from theprevious approaches known in literature. In fact, approximation algorithms developed in the past mostly relate on computing bounds on the global cost of anoptimal solution, e.g. showing that an approximate solution constructed out ofseveral matchings or Steiner trees, has a total cost that is not that far from theoptimum