@inproceedings{634fe208ee294614a9881b8ed2c17656,
title = "A note on iterated rounding for the survivable network design problem",
abstract = "In this note we consider the survivable network design problem (SNDP) in undirected graphs. We make two contributions. The first is a new counting argument in the iterated rounding based 2-approximation for edge-connectivity SNDP (EC-SNDP) originally due to Jain [10]. The second contribution is to make some connections between hypergraphic version of SNDP (Hypergraph-SNDP) introduced in [17] and edge and node-weighted versions of EC-SNDP and element-connectivity SNDP (Elem-SNDP). One useful consequence is a 2-approximation for Elem-SNDP that avoids the use of set-pair based relaxation and analysis.",
keywords = "Approximation, Element connectivity, Iterated rounding, Survivable network design",
author = "Chandra Chekuri and Thapanapong Rukkanchanunt",
note = "Publisher Copyright: {\textcopyright} Chandra Chekuri and Thapanapong Rukkanchanunt.; 1st Symposium on Simplicity in Algorithms, SOSA 2018 ; Conference date: 07-01-2018 Through 10-01-2018",
year = "2018",
month = jan,
day = "1",
doi = "10.4230/OASIcs.SOSA.2018.2",
language = "English (US)",
series = "OpenAccess Series in Informatics",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Raimund Seidel",
booktitle = "1st Symposium on Simplicity in Algorithms, SOSA 2018 - Co-located with the 29th ACM-SIAM Symposium on Discrete Algorithms, SODA 2018",
}