DROPS

Document

DOI: 10.4230/OASIcs.SOSA.2018.2

A Note on Iterated Rounding for the Survivable Network Design Problem

Authors: Chandra Chekuri and Thapanapong Rukkanchanunt

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)

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.

Cite as

Chandra Chekuri and Thapanapong Rukkanchanunt. A Note on Iterated Rounding for the Survivable Network Design Problem. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:OASIcs.SOSA.2018.2,
  author =	{Chekuri, Chandra and Rukkanchanunt, Thapanapong},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.2},
  URN =		{urn:nbn:de:0030-drops-82976},
  doi =		{10.4230/OASIcs.SOSA.2018.2},
  annote =	{Keywords: survivable network design, iterated rounding, approximation, element connectivity}
}

Search Results

Documents authored by Rukkanchanunt, Thapanapong

A Note on Iterated Rounding for the Survivable Network Design Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message