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

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorBeyer, Stephanen_US
dc.contributor.authorChimani, Markusen_US
dc.contributor.authorSpoerhase, Joachimen_US
dc.contributor.departmentOsnabrück Universityen_US
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.contributor.editorKim, Donghyunen_US
dc.contributor.editorUma, R.N.en_US
dc.contributor.editorCai, Zhipengen_US
dc.contributor.editorLee, Dong Hoonen_US
dc.date.accessioned2020-10-16T08:10:32Z
dc.date.available2020-10-16T08:10:32Z
dc.date.issued2020-01-01en_US
dc.description| openaire: EC/H2020/759557/EU//ALGOCom
dc.description.abstractOur 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.en
dc.description.versionPeer revieweden
dc.format.extent13
dc.format.extent347-359
dc.identifier.citationBeyer , 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_28en
dc.identifier.doi10.1007/978-3-030-58150-3_28en_US
dc.identifier.isbn9783030581497
dc.identifier.issn0302-9743
dc.identifier.issn1611-3349
dc.identifier.otherPURE UUID: efa27af2-c606-4473-9b3c-a1d863e4e4ecen_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/efa27af2-c606-4473-9b3c-a1d863e4e4ecen_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85091104639&partnerID=8YFLogxKen_US
dc.identifier.otherPURE LINK: https://arxiv.org/abs/1808.04651en_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/47000
dc.identifier.urnURN:NBN:fi:aalto-202010165897
dc.language.isoenen
dc.publisherSpringer
dc.relationinfo:eu-repo/grantAgreement/EC/H2020/759557/EU//ALGOComen_US
dc.relation.ispartofInternational Computing and Combinatorics Conferenceen
dc.relation.ispartofseriesComputing and Combinatorics - 26th International Conference, COCOON 2020, Proceedingsen
dc.relation.ispartofseriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en
dc.relation.ispartofseriesVolume 12273 LNCSen
dc.rightsopenAccessen
dc.titleA Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphsen
dc.typeConference article in proceedingsfi
Files