License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2018.2
URN: urn:nbn:de:0030-drops-82976
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8297/
Chekuri, Chandra ;
Rukkanchanunt, Thapanapong
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. The second contribution is to make some connections between hypergraphic version of SNDP (Hypergraph-SNDP) introduced by Zhao, Nagamochi and Ibaraki, 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.
BibTeX - Entry
@InProceedings{chekuri_et_al:OASIcs:2018:8297,
author = {Chandra Chekuri and Thapanapong Rukkanchanunt},
title = {{A Note on Iterated Rounding for the Survivable Network Design Problem}},
booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)},
pages = {2:1--2:10},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-064-4},
ISSN = {2190-6807},
year = {2018},
volume = {61},
editor = {Raimund Seidel},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8297},
URN = {urn:nbn:de:0030-drops-82976},
doi = {10.4230/OASIcs.SOSA.2018.2},
annote = {Keywords: survivable network design, iterated rounding, approximation, element connectivity}
}
|
Keywords: |
|
survivable network design, iterated rounding, approximation, element connectivity |
|
Collection: |
|
1st Symposium on Simplicity in Algorithms (SOSA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
05.01.2018 |
