Fast Approximation Algorithms for the Generalized Survivable Network Design Problem

DOI10.4230/LIPICS.ISAAC.2016.33MaRDI QIDQ4636516zbMATH OpenFDO

Authors Andreas Emil Feldmann, Jochen Könemann, Kanstantsin Pashkovich, Laura Sanità

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1604.07049

zbMATH Keywords

primal-dual methodgeneralized survivable network designstrongly polynomial runtime

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Abstract: In a standard $f$-connectivity network design problem, we are given an undirected graph $G=(V,E)$, a cut-requirement function $f:2^{V}ightarrowmathbbN$, and non-negative costs $c(e)$ for all $einE$. We are then asked to find a minimum-cost vector $xin{mathbbN}^E$ such that $x(delta(S))geqf(S)$ for all $SsubseteqV$. 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).

Recommendations

• scientific article; zbMATH DE number 1263260
• An efficient approximation algorithm for the survivable network design problem
• Fast exact algorithms for survivable network design with uniform requirements
• Fast exact algorithms for survivable network design with uniform requirements
• scientific article; zbMATH DE number 2086687
• scientific article; zbMATH DE number 1788731
• A primal-dual approximation algorithm for the survivable network design problem in hypergraphs
• scientific article; zbMATH DE number 1688385
• Strong lower bounds for a survivable network design problem
• Parameterized algorithms for survivable network design with uniform demands

Cited in

(5)

• Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
• Single-sink fractionally subadditive network design
• Node-connectivity terminal backup, separately-capacitated multiflow, and discrete convexity
• A fast approximation scheme for fractional covering problems with variable upper bounds
• An efficient approximation algorithm for the survivable network design problem

This page was built for publication: Fast Approximation Algorithms for the Generalized Survivable Network Design Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636516)