Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

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

Loading next page...
/lp/association-for-computing-machinery/the-vpn-conjecture-is-true-ppQc99oq1y

References (34)

Datasource
Association for Computing Machinery
Copyright
Copyright © 2008 by ACM Inc.
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.