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
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.
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

Page view(s)

Last Week
Last month
checked on Jun 25, 2024

Google ScholarTM