000138778 001__ 138778
000138778 005__ 20190117210912.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__ $$aBerlin$$bSpringer$$c2009
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$$aRothvoß, Thomas$$g183730
000138778 700__ $$0243827$$aSanità, Laura$$g190471
000138778 7112_ $$a12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09)$$cUC Berkeley, USA$$dAugust 21-23, 2009
000138778 773__ $$q326-338$$t12th Intl. Workshop on Approximation Algorithms for Combinat
000138778 8564_ $$uhttp://cui.unige.ch/tcs/random-approx/2009/index.php$$zURL
000138778 8564_ $$s178299$$uhttps://infoscience.epfl.ch/record/138778/files/vpn.pdf$$yn/a$$zn/a
000138778 909C0 $$0252111$$pDISOPT$$xU11879
000138778 909CO $$ooai:infoscience.tind.io:138778$$pconf$$pGLOBAL_SET$$pSB
000138778 917Z8 $$x183730
000138778 937__ $$aDISOPT-CONF-2009-006
000138778 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000138778 980__ $$aCONF