000138778 001__ 138778
000138778 005__ 20190617200631.0
000138778 0247_ $$2doi$$a10.1007/978-3-642-03685-9_25
000138778 02470 $$2ISI$$a000269953900025
000138778 037__ $$aCONF
000138778 245__ $$aOn the Complexity of the Asymmetric VPN Problem
000138778 269__ $$a2009
000138778 260__ $$bSpringer$$c2009$$aBerlin
000138778 336__ $$aConference Papers
000138778 490__ $$aLecture Notes in Computer Science$$v5687
000138778 520__ $$aWe give the first constant factor approximation algorithm for the asymmetric Virtual Private Network (VPN) problem with arbitrary concave costs. We even show the stronger result, that there is always a tree solution of cost at most 2 OPT and that a tree solution of (expected) cost at most 49.84 OPT can be determined in polynomial time. Furthermore, we answer an outstanding open question about the complexity status of the so called balanced VPN problem by proving its NP-hardness.
000138778 6531_ $$aNetwork design
000138778 6531_ $$aapproximation algorithms
000138778 6531_ $$aNP-hardness
000138778 700__ $$0243826$$g183730$$aRothvoß, Thomas
000138778 700__ $$g190471$$aSanità, Laura$$0243827
000138778 7112_ $$dAugust 21-23, 2009$$cUC Berkeley, USA$$a12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09)
000138778 773__ $$t12th Intl. Workshop on Approximation Algorithms for Combinat$$q326-338
000138778 8564_ $$uhttp://cui.unige.ch/tcs/random-approx/2009/index.php$$zURL
000138778 8564_ $$uhttps://infoscience.epfl.ch/record/138778/files/vpn.pdf$$zn/a$$s178299$$yn/a
000138778 909C0 $$xU11879$$0252111$$pDISOPT
000138778 909CO $$ooai:infoscience.tind.io:138778$$qGLOBAL_SET$$pconf$$pSB
000138778 917Z8 $$x183730
000138778 937__ $$aDISOPT-CONF-2009-006
000138778 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000138778 980__ $$aCONF