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...
Saved in:
Main Authors: | , |
---|---|
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 |