The VPN problem with concave costs

Samuel Fiorini, Gianpaolo Oriolo, Laura Sanità, Dirk Oliver Theis

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)


Only recently Goyal, Olver, and Shepherd [Pr oc. 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.

Original languageEnglish
Pages (from-to)1080-1090
Number of pages11
JournalSIAM Journal on Discrete Mathematics
Issue number3
Publication statusPublished - 2010
Externally publishedYes


  • Approximation algorithm
  • Concave cost
  • Network design
  • Routing problem


Dive into the research topics of 'The VPN problem with concave costs'. Together they form a unique fingerprint.

Cite this