TY - GEN

T1 - Fast approximation algorithms for the generalized survivable network design problem

AU - Feldmann, Andreas Emil

AU - Könemann, Jochen

AU - Pashkovich, Kanstantsin

AU - Sanità, Laura

PY - 2016/12/1

Y1 - 2016/12/1

N2 - In a standard f-connectivity network design problem, we are given an undirected graph G = (V, E), a cut-requirement function f : 2V → N, and non-negative costs c(e) for all e ∈ E. We are then asked to find a minimum-cost vector x ∈ ℕE such that x(δ(S)) ≥ f(S) for all S ⊆ 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 + ε)-approximation for the generalized survivable network design problem (where we consider rounding up of rationals an arithmetic operation).

AB - In a standard f-connectivity network design problem, we are given an undirected graph G = (V, E), a cut-requirement function f : 2V → N, and non-negative costs c(e) for all e ∈ E. We are then asked to find a minimum-cost vector x ∈ ℕE such that x(δ(S)) ≥ f(S) for all S ⊆ 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 + ε)-approximation for the generalized survivable network design problem (where we consider rounding up of rationals an arithmetic operation).

KW - Generalized survivable network design

KW - Primal-dual method

KW - Strongly polynomial runtime

UR - http://www.scopus.com/inward/record.url?scp=85010723569&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2016.33

DO - 10.4230/LIPIcs.ISAAC.2016.33

M3 - Conference contribution

AN - SCOPUS:85010723569

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 33.1-33.12

BT - 27th International Symposium on Algorithms and Computation, ISAAC 2016

A2 - Hong, Seok-Hee

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 27th International Symposium on Algorithms and Computation, ISAAC 2016

Y2 - 12 December 2016 through 14 December 2016

ER -