THE VPN PROBLEM WITH CONCAVE COSTS

作     者：Fiorini, Samuel Oriolo, Gianpaolo Sanita, Laura Theis, Dirk Oliver 

作者机构：Univ Libre Bruxelles Dept Math Brussels Belgium Univ Roma Tor Vergata Dipartimento Ing Impresa Rome Italy 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：2010年第24卷第3期

页      面：1080-1090页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Communaute francaise de Belgique Fonds National de la Recherche Scientifique (F.R.S.FNRS) Swiss National Science Foundation 

主　　题：network design routing problem approximation algorithm concave cost 

摘      要：Only recently Goyal, Olver, and Shepherd [Proc. STOC, ACM, New York, 2008] proved that the symmetric virtual private network design (sVPN) problem has the tree routing property, namely, that there always exists an optimal solution to the problem whose support is a tree. Combining this with previous results by Fingerhut, Suri, and Turner [J. Algorithms, 24 (1997), pp. 287-309] and Gupta et al. [Proc. STOC, ACM, New York, 2001], sVPN can be solved in polynomial time. In this paper we investigate an APX-hard generalization of sVPN, where the contribution of each edge to the total cost is proportional to some non-negative, concave, and nondecreasing function of the capacity reservation. We show that the tree routing property extends to the new problem and give a constant-factor approximation algorithm for it. We also show that the undirected uncapacitated single-source minimum concave-cost flow problem has the tree routing property when the cost function has some property of symmetry.