Projects per year
Abstract
Our paper is motivated by the search for combinatorial and, in particular, primaldual approximation algorithms for higherconnectivity survivable network design problems (SND). The best known approximation algorithm for SND is Jain’s powerful but “noncombinatorial” iterative LProunding technique, which yields factor 2. In contrast, known combinatorial algorithms are based on multiphase primaldual 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 singlephase primaldual algorithms for such problems. A singlephase primaldual algorithm could potentially be key to a primaldual constantfactor 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 primaldual algorithm for the minimum 2edgeconnected spanning subgraph problem (2ECSS) that requires only a single growing phase and that is therefore the first such algorithm for any higherconnectivity problem. The algorithm yields approximation factor 3, which matches the factor of the best known (twophase) primaldual approximation algorithms for 2ECSS. Moreover, we believe that our algorithm is more natural and conceptually simpler than the known primaldual algorithms for 2ECSS. It can be implemented without data structures more sophisticated than binary heaps and graphs, and without graph algorithms beyond depthfirst search.
Original language  English 

Title of host publication  Computing and Combinatorics  26th International Conference, COCOON 2020, Proceedings 
Editors  Donghyun Kim, R.N. Uma, Zhipeng Cai, Dong Hoon Lee 
Publisher  SPRINGER 
Pages  347359 
Number of pages  13 
ISBN (Print)  9783030581497 
DOIs  
Publication status  Published  1 Jan 2020 
MoE publication type  A4 Article in a conference publication 
Event  International Computing and Combinatorics Conference  Atlanta, United States Duration: 29 Aug 2020 → 31 Aug 2020 Conference number: 26 
Publication series
Name  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 

Publisher  Springer 
Volume  12273 LNCS 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  International Computing and Combinatorics Conference 

Abbreviated title  COCOON 
Country/Territory  United States 
City  Atlanta 
Period  29/08/2020 → 31/08/2020 
Fingerprint
Dive into the research topics of 'A Simple PrimalDual Approximation Algorithm for 2EdgeConnected Spanning Subgraphs'. Together they form a unique fingerprint.Projects
 1 Active

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Jindal, G., Franck, M., Spoerhase, J., Yingchareonthawornchai, S., Gadekar, A., Orgo, L., Jiamjitrak, W. & Khodamoradi, K.
01/02/2018 → 31/01/2024
Project: EU: ERC grants