2026-07-20T11:02:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6803 2024-03-06T10:38:55Z ddc:004 open_access

Fast Approximation Algorithms for the Generalized Survivable Network Design Problem Feldmann, Andreas Emil Könemann, Jochen Pashkovich, Kanstantsin Sanità, Laura strongly polynomial runtime generalized survivable network design primal-dual method In a standard f-connectivity network design problem, we are given an undirected graph G = (V, E), a cut-requirement function f : 2^V to N, and non-negative costs c(e) for all e in E. We are then asked to find a minimum-cost vector x in N^E such that x(delta(S)) geq f (S) for all S subseteq V. We focus on the class of such problems where f is a proper function. This encodes many well-studied NP-hard problems such as the generalized survivable network design problem. In this paper we present the first strongly polynomial time FPTAS for solving the LP relaxation of the standard IP formulation of the f-connectivity problem with general proper functions f. Implementing Jain’s algorithm, this yields a strongly polynomial time (2 + epsilon)-approximation for the generalized survivable network design problem (where we consider rounding up of rationals an arithmetic operation). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Emil Feldmann and Jochen Könemann and Kanstantsin Pashkovich and Laura Sanità 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.33 urn:nbn:de:0030-drops-68035 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.33 eng https://creativecommons.org/licenses/by/3.0/legalcode