# The VPN conjecture is true

The VPN conjecture is true The VPN Conjecture is True Navin Goyal College of Computing Georgia Institute of Technology Atlanta, GA, USA Neil Olver Department of Mathematics and Statistics McGill University Montreal, QC, Canada F. B. Shepherd Department of Mathematics and Statistics McGill University Montreal, QC, Canada navin001@gmail.com ABSTRACT olver@math.mcgill.ca bruce.shepherd@mcgill.ca We consider the following network design problem. We are given an undirected graph G = (V, E) with edges costs c(e) and a set of terminal nodes W . A hose demand matrix for W is any symmetric matrix [Dij ] such that for each i, P j=i Dij ¤ 1. We must compute the minimum cost edge capacities that are able to support the oblivious routing of every hose matrix in the network. An oblivious routing template, in this context, is a simple path Pij for each pair i, j ˆ W . Given such a template, if we are to route a demand matrix D, then for each i, j we send Dij units of ‚ow along each Pij . Fingerhut et al. [12] and Gupta et al. [15] obtained a 2-approximation for this problem, using a solution template in the form of a tree. It has been widely asked http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

# The VPN conjecture is true

Association for Computing Machinery — May 17, 2008
7 pages

/lp/association-for-computing-machinery/the-vpn-conjecture-is-true-ppQc99oq1y

# References (34)

Datasource
Association for Computing Machinery
ISBN
978-1-60558-047-0
doi
10.1145/1374376.1374440
Publisher site
See Article on Publisher Site

### Abstract

The VPN Conjecture is True Navin Goyal College of Computing Georgia Institute of Technology Atlanta, GA, USA Neil Olver Department of Mathematics and Statistics McGill University Montreal, QC, Canada F. B. Shepherd Department of Mathematics and Statistics McGill University Montreal, QC, Canada navin001@gmail.com ABSTRACT olver@math.mcgill.ca bruce.shepherd@mcgill.ca We consider the following network design problem. We are given an undirected graph G = (V, E) with edges costs c(e) and a set of terminal nodes W . A hose demand matrix for W is any symmetric matrix [Dij ] such that for each i, P j=i Dij ¤ 1. We must compute the minimum cost edge capacities that are able to support the oblivious routing of every hose matrix in the network. An oblivious routing template, in this context, is a simple path Pij for each pair i, j ˆ W . Given such a template, if we are to route a demand matrix D, then for each i, j we send Dij units of ‚ow along each Pij . Fingerhut et al. [12] and Gupta et al. [15] obtained a 2-approximation for this problem, using a solution template in the form of a tree. It has been widely asked

### There are no references for this article.

Access the full text.

Sign up today, get DeepDyve free for 14 days.