{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:21Z","timestamp":1759638681365,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MELS Quebec Merit Scholarship for Foreign Students"},{"name":"Schulich Fellowship"},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,6]]},"abstract":"<jats:p>\n            We consider the following network design problem. We are given an undirected graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) with edge costs\n            <jats:italic>c<\/jats:italic>\n            (\n            <jats:italic>e<\/jats:italic>\n            ) and a set of terminal nodes\n            <jats:italic>W<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            . A\n            <jats:italic>hose<\/jats:italic>\n            demand matrix is any symmetric matrix\n            <jats:italic>D<\/jats:italic>\n            , indexed by the terminals, such that for each\n            <jats:italic>i<\/jats:italic>\n            \u2208\n            <jats:italic>W<\/jats:italic>\n            , \u2211\n            <jats:sub>j\u2260i<\/jats:sub>\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>ij<\/jats:sub>\n            \u2264 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\n            <jats:italic>oblivious routing<\/jats:italic>\n            template, in this context, is a simple path\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>ij<\/jats:sub>\n            for each pair\n            <jats:italic>i,j<\/jats:italic>\n            \u2208\n            <jats:italic>W<\/jats:italic>\n            . Given such a template, if we are to route a demand matrix\n            <jats:italic>D<\/jats:italic>\n            , then for each\n            <jats:italic>i,j<\/jats:italic>\n            , we send\n            <jats:italic>D<\/jats:italic>\n            <jats:sub>ij<\/jats:sub>\n            units of flow along each\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>ij<\/jats:sub>\n            . Fingerhut et al. [1997] and Gupta et al. [2001] obtained a 2-approximation for this problem, using a solution template in the form of a tree. It has been widely asked and subsequently conjectured [Italiano et al. 2006] that this solution actually results in the optimal capacity for the single-path VPN design problem; this has become known as the\n            <jats:italic>VPN Conjecture<\/jats:italic>\n            . The conjecture has previously been proven for some restricted classes of graphs [Fingerhut et al. 1997; Fiorini et al. 2007; Grandoni et al. 2008; Hurkens et al. 2007]. Our main theorem establishes that this conjecture is true in general graphs. This also has the implication that the single-path VPN problem is solvable in polynomial time.\n          <\/jats:p>\n          <jats:p>A natural fractional version of the conjecture had also been proposed [Hurkens et al. 2007]. In this version, the routing may split flow between many paths, in specified proportions. We demonstrate that this multipath version of the conjecture is in fact false. The multipath and single path versions of the VPN problem are essentially direct analogues of the randomized and nonrandomized versions of oblivious routing schemes for minimizing congestion for permutation routing [Borodin and Hopcroft 1982; Valiant 1982].<\/jats:p>","DOI":"10.1145\/2487241.2487243","type":"journal-article","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T14:32:49Z","timestamp":1372775569000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["The VPN Conjecture Is True"],"prefix":"10.1145","volume":"60","author":[{"given":"Navin","family":"Goyal","sequence":"first","affiliation":[{"name":"Microsoft Research"}]},{"given":"Neil","family":"Olver","sequence":"additional","affiliation":[{"name":"MIT"}]},{"given":"F. Bruce","family":"Shepherd","sequence":"additional","affiliation":[{"name":"McGill University"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1002\/net.v49:1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/777313.777314"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1007\/s11081-005-1741-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1287\/moor.23.4.769"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1016\/S0167-6377(99)00016-4"},{"doi-asserted-by":"crossref","unstructured":"Ben-Tal A. El Ghaoui L. and Nemirovski A. 2009. Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press.  Ben-Tal A. El Ghaoui L. and Nemirovski A. 2009. Robust Optimization . Princeton Series in Applied Mathematics. Princeton University Press.","key":"e_1_2_1_6_1","DOI":"10.1515\/9781400831050"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1007\/s10107-003-0396-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/800070.802209"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1002\/net.v50:1"},{"doi-asserted-by":"crossref","unstructured":"Cook W. J. Cunningham W. H. Pulleyblank W. R. and Schrijver A. 1997. Combinatorial Optimization 1st Ed. Wiley-Interscience.   Cook W. J. Cunningham W. H. Pulleyblank W. R. and Schrijver A. 1997. Combinatorial Optimization 1st Ed. Wiley-Interscience.","key":"e_1_2_1_10_1","DOI":"10.1002\/9781118033142"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/316188.316209"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM","author":"Eisenbrand F.","unstructured":"Eisenbrand , F. and Grandoni , F . 2005. An improved approximation algorithm for virtual private network design . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM , Philadelphia, PA, 928--932. Eisenbrand, F. and Grandoni, F. 2005. An improved approximation algorithm for virtual private network design. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 928--932.","key":"e_1_2_1_12_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1007\/11758471_13"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1137\/060654827"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1137\/S0895479896298130"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1137\/S1052623496305717"},{"volume-title":"Proceedings of INFOCOM. 2275--2282","author":"Erlebach T.","unstructured":"Erlebach , T. and R\u00fcegg , M . 2004. Optimal bandwidth reservation in hose-model VPNs with multi-path routing . In Proceedings of INFOCOM. 2275--2282 . Erlebach, T. and R\u00fcegg, M. 2004. Optimal bandwidth reservation in hose-model VPNs with multi-path routing. In Proceedings of INFOCOM. 2275--2282.","key":"e_1_2_1_17_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1006\/jagm.1997.0866"},{"unstructured":"Fiorini S. Oriolo G. Sanit\u00e0 L. and Theis D. O. 2007. The VPN tree routing conjecture for outerplanar networks. arXiv:0711.2623v3 {math.OC}.  Fiorini S. Oriolo G. Sanit\u00e0 L. and Theis D. O. 2007. The VPN tree routing conjecture for outerplanar networks. arXiv:0711.2623v3 {math.OC}.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1137\/090749700"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1016\/j.orl.2007.10.008"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.5555\/1880918.1880972"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/380752.380830"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/780542.780597"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1137\/050626259"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1016\/j.orl.2005.09.005"},{"key":"e_1_2_1_27_1","first-page":"223","article-title":"Tight bounds for oblivious routing in the hypercube","volume":"24","author":"Kaklamanis C.","year":"1991","unstructured":"Kaklamanis , C. , Krizanc , D. , and Tsantilas , T. 1991 . Tight bounds for oblivious routing in the hypercube . Theory Comput. Syst. 24 , 1, 223 -- 232 . Kaklamanis, C., Krizanc, D., and Tsantilas, T. 1991. Tight bounds for oblivious routing in the hypercube. Theory Comput. Syst. 24, 1, 223--232.","journal-title":"Theory Comput. Syst."},{"doi-asserted-by":"crossref","unstructured":"Kouvelis P. and Yu G. 1997. Robust Discrete Optimization and Its Applications (Nonconvex Optimization and Its Applications) 1st Ed. Springer.  Kouvelis P. and Yu G. 1997. Robust Discrete Optimization and Its Applications (Nonconvex Optimization and Its Applications) 1st Ed. Springer.","key":"e_1_2_1_28_1","DOI":"10.1007\/978-1-4757-2620-6_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1109\/TNET.2002.802141"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/331524.331526"},{"volume-title":"Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). 1097--1105","author":"Olver N.","unstructured":"Olver , N. and Shepherd , F. B . 2010. Approximability of robust network design . In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). 1097--1105 . Olver, N. and Shepherd, F. B. 2010. Approximability of robust network design. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). 1097--1105.","key":"e_1_2_1_31_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.5555\/645413.652152"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1145\/1374376.1374415"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1007\/978-3-642-03685-9_25"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1137\/0211027"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/800076.802479"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2487241.2487243","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2487241.2487243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:39Z","timestamp":1750236519000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2487241.2487243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["10.1145\/2487241.2487243"],"URL":"https:\/\/doi.org\/10.1145\/2487241.2487243","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2010-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}