License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.33
URN: urn:nbn:de:0030-drops-68035
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6803/
Go to the corresponding LIPIcs Volume Portal

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

Fast Approximation Algorithms for the Generalized Survivable Network Design Problem

pdf-format:
LIPIcs-ISAAC-2016-33.pdf (0.5 MB)

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 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).

BibTeX - Entry

@InProceedings{feldmann_et_al:LIPIcs:2016:6803,
  author =	{Andreas Emil Feldmann and Jochen K{\"o}nemann and Kanstantsin Pashkovich and Laura Sanit{\`a}},
  title =	{{Fast Approximation Algorithms for the Generalized Survivable Network Design Problem}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{33:1--33:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6803},
  URN =		{urn:nbn:de:0030-drops-68035},
  doi =		{10.4230/LIPIcs.ISAAC.2016.33},
  annote =	{Keywords: strongly polynomial runtime, generalized survivable network design, primal-dual method}
}

Keywords: strongly polynomial runtime, generalized survivable network design, primal-dual method
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI