1 Search Results for "Rukkanchanunt, Thapanapong"


Document
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-dev.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}
}
  • Refine by Author
  • 1 Chekuri, Chandra
  • 1 Rukkanchanunt, Thapanapong

  • Refine by Classification

  • Refine by Keyword
  • 1 approximation
  • 1 element connectivity
  • 1 iterated rounding
  • 1 survivable network design

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail