License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2017.21
URN: urn:nbn:de:0030-drops-86475
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8647/
Censor-Hillel, Keren ;
Dory, Michal
Fast Distributed Approximation for TAP and 2-Edge-Connectivity
Abstract
The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G, such that T ∪ Aug is 2-edge-connected.
TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and JáJá, SICOMP 1981. Recently, a 3/2-approximation was given for the unweighted case by Kortsarz and Nutov, TALG 2016, and recent breakthroughs by Adjiashvili, SODA 2017, and by Fiorini et al., 2017, give approximations better than 2 for bounded weights.
In this paper, we provide the first fast distributed approximations for TAP. We present a distributed 2-approximation for weighted TAP which completes in O(h) rounds, where h is the height of T . When h is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in O(D + (√n) log^{*} n) rounds, where n is the number of vertices and D is the diameter of G.
Immediate consequences of our results are an O(D)-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an O(hMST + (√n)log^{*} n)-round 3- approximation algorithm for the weighted case, where hMST is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augment- ing the connectivity of any connected spanning subgraph to 2.
Finally, we complement our study with proving lower bounds for distributed approximations of TAP.
BibTeX - Entry
@InProceedings{censorhillel_et_al:LIPIcs:2018:8647,
author = {Keren Censor-Hillel and Michal Dory},
title = {{Fast Distributed Approximation for TAP and 2-Edge-Connectivity}},
booktitle = {21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
pages = {21:1--21:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-061-3},
ISSN = {1868-8969},
year = {2018},
volume = {95},
editor = {James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8647},
URN = {urn:nbn:de:0030-drops-86475},
doi = {10.4230/LIPIcs.OPODIS.2017.21},
annote = {Keywords: approximation algorithms, distributed network design, connectivity augmentation}
}
|
Keywords: |
|
approximation algorithms, distributed network design, connectivity augmentation |
|
Collection: |
|
21st International Conference on Principles of Distributed Systems (OPODIS 2017) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
28.03.2018 |
