I en standard f-konnektivitet nätverk design problem, vi ges en oriktad graf G = (V, E), en cut-requiredment funktion f : 2 V → N, och icke-negativa kostnader c (e) för alla e E. Vi blir sedan ombedda att hitta en minsta kostnad vektor x  på N E sådan att x(σ(S)) ≥ f (S) för alla S  på V. Vi fokuserar på klassen av sådana problem där f är en riktig funktion. Detta kodar många välstuderade NP-hårda problem såsom den generaliserade överlevnadsbara nätverksdesign problem. I detta papper presenterar vi den första starkt polynom tid FPTAS för att lösa LP avslappning av standard IP-formuleringen av f -kopplingsproblem med allmänna korrekta funktioner f. Genomföra Jains algoritm, detta ger en starkt polynom tid (2 +  på) - approximation för den generaliserade Survivalable nätverk design problem (där vi anser avrundning upp av rationella en aritmetisk operation ).
Nyligen, en starkt-polynom tid FPTAS att lösa LP-avslappning av (IP) med lämpliga funktioner har getts i REF.
Fast Approximation Algorithms for the Generalized Survivable Network Design Problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}