A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs
No Thumbnail Available
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2020-01-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
13
Series
Computing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings, pp. 347-359, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) ; Volume 12273 LNCS
Abstract
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 factor 2. 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 factor 3, 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.Description
| openaire: EC/H2020/759557/EU//ALGOCom
Keywords
Other note
Citation
Beyer, S, Chimani, M & Spoerhase, J 2020, A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs. in D Kim, R N Uma, Z Cai & D H Lee (eds), Computing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12273 LNCS, Springer, pp. 347-359, International Computing and Combinatorics Conference, Atlanta, Georgia, United States, 29/08/2020. https://doi.org/10.1007/978-3-030-58150-3_28