## Abstract

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 language | English |
---|---|

Pages (from-to) | 1080-1090 |

Number of pages | 11 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 24 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2010 |

Externally published | Yes |

## Keywords

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