A note on iterated rounding for the survivable network design problem

© Chandra Chekuri and Thapanapong Rukkanchanunt. 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...

Full description

Saved in:
Bibliographic Details
Main Authors: Chandra Chekuri, Thapanapong Rukkanchanunt
Format: Conference Proceeding
Published: 2018
Subjects:
Online Access:https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85040686269&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/58837
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Chiang Mai University
id th-cmuir.6653943832-58837
record_format dspace
spelling th-cmuir.6653943832-588372018-09-05T04:40:50Z A note on iterated rounding for the survivable network design problem Chandra Chekuri Thapanapong Rukkanchanunt Mathematics Social Sciences © Chandra Chekuri and Thapanapong Rukkanchanunt. 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. 2018-09-05T04:33:36Z 2018-09-05T04:33:36Z 2018-01-01 Conference Proceeding 21906807 2-s2.0-85040686269 10.4230/OASIcs.SOSA.2018.2 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85040686269&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/58837
institution Chiang Mai University
building Chiang Mai University Library
country Thailand
collection CMU Intellectual Repository
topic Mathematics
Social Sciences
spellingShingle Mathematics
Social Sciences
Chandra Chekuri
Thapanapong Rukkanchanunt
A note on iterated rounding for the survivable network design problem
description © Chandra Chekuri and Thapanapong Rukkanchanunt. 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.
format Conference Proceeding
author Chandra Chekuri
Thapanapong Rukkanchanunt
author_facet Chandra Chekuri
Thapanapong Rukkanchanunt
author_sort Chandra Chekuri
title A note on iterated rounding for the survivable network design problem
title_short A note on iterated rounding for the survivable network design problem
title_full A note on iterated rounding for the survivable network design problem
title_fullStr A note on iterated rounding for the survivable network design problem
title_full_unstemmed A note on iterated rounding for the survivable network design problem
title_sort note on iterated rounding for the survivable network design problem
publishDate 2018
url https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85040686269&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/58837
_version_ 1681425139923681280