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

Stephan Beyer, Markus Chimani, Joachim Spoerhase*

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu


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.

OtsikkoComputing and Combinatorics - 26th International Conference, COCOON 2020, Proceedings
ToimittajatDonghyun Kim, R.N. Uma, Zhipeng Cai, Dong Hoon Lee
ISBN (painettu)9783030581497
DOI - pysyväislinkit
TilaJulkaistu - 1 tammik. 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
Tapahtuma International Computing and Combinatorics Conference - Atlanta, Yhdysvallat
Kesto: 29 elok. 202031 elok. 2020
Konferenssinumero: 26


NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta12273 LNCS
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349


Conference International Computing and Combinatorics Conference


Sukella tutkimusaiheisiin 'A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä