Projects per year

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

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 Science and Business Media Deutschland GmbH |

Pages | 347-359 |

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) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | International Computing and Combinatorics Conference |
---|---|

Abbreviated title | COCOON |

Country | United States |

City | Atlanta |

Period | 29/08/2020 → 31/08/2020 |

## Fingerprint Dive into the research topics of 'A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs'. Together they form a unique fingerprint.

## Projects

- 1 Active

## ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics

Chalermsook, P., Spoerhase, J., Orgo, L. & Yingchareonthawornchai, S.

01/02/2018 → 31/08/2023

Project: EU: ERC grants

## Cite this

*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); Vol. 12273 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-58150-3_28