## A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs

Autor(en): | Beyer, S. Chimani, M. Spoerhase, J. |

Herausgeber: | Kim, D. Uma, R.N. Cai, Z. Lee, D.H. |

Stichwörter: | Combinatorial mathematics; Graph algorithms; Iterative methods, Approximation factor; Combinatorial algorithm; Connectivity problems; Constant-factor approximation algorithms; Primal dual algorithms; Primal-dual approach; Primal-dual approximation algorithm; Survivable network design, Approximation algorithms |

Erscheinungsdatum: | 2020 |

Herausgeber: | Springer Science and Business Media Deutschland GmbH |

Enthalten in: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Band: | 12273 LNCS |

Startseite: | 347 |

Seitenende: | 359 |

Zusammenfassung: | Our paper is motivated by the search for combinatorial and, in particular, primal-dual approximation algorithms for higher-connectivity survivable network design problems (SND). The best known approximation algorithm for SND is Jain's powerful but “non-combinatorial” iterative LP-rounding technique, which yields factor2. In contrast, known combinatorial algorithms are based on multi-phase primal-dual approaches that increase the connectivity in each phase, thereby naturally leading to a factor depending (logarithmically) on the maximum connectivity requirement. Williamson raised the question if there are single-phase primal-dual algorithms for such problems. A single-phase primal-dual algorithm could potentially be key to a primal-dual constant-factor approximation algorithm for SND. Whether such an algorithm exists is an important open problem (Shmoys and Williamson). In this paper, we make a first, small step related to these questions. We show that there is a primal-dual algorithm for the minimum 2-edge-connected spanning subgraph problem (2ECSS) that requires only a single growing phase and that is therefore the first such algorithm for any higher-connectivity problem. The algorithm yields approximation factor3, which matches the factor of the best known (two-phase) primal-dual approximation algorithms for 2ECSS. Moreover, we believe that our algorithm is more natural and conceptually simpler than the known primal-dual algorithms for 2ECSS. It can be implemented without data structures more sophisticated than binary heaps and graphs, and without graph algorithms beyond depth-first search. © 2020, Springer Nature Switzerland AG. |

Beschreibung: | Conference of 26th International Conference on Computing and Combinatorics, COCOON 2020 ; Conference Date: 29 August 2020 Through 31 August 2020; Conference Code:244449 |

ISBN: | 9783030581497 |

ISSN: | 03029743 |

DOI: | 10.1007/978-3-030-58150-3_28 |

Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85091104639&doi=10.1007%2f978-3-030-58150-3_28&partnerID=40&md5=e56d2fc3a590dc9b744088fc33458100 |

Show full item record