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.5
URN: urn:nbn:de:0030-drops-86262
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8626/
Dinitz, Michael ;
Nazari, Yasamin
Distributed Distance-Bounded Network Design Through Distributed Convex Programming
Abstract
Solving linear programs is often a challenging task in distributed settings. While there are good algorithms for solving packing and covering linear programs in a distributed manner (Kuhn et al. 2006), this is essentially the only class of linear programs for which such an algorithm is known. In this work we provide a distributed algorithm for solving a different class of convex programs which we call “distance-bounded network design convex programs”. These can be thought of as relaxations of network design problems in which the connectivity requirement includes a distance constraint (most notably, graph spanners). Our algorithm runs in O((D/ε) log n) rounds in the LOCAL model and with high probability finds a (1+ε)-approximation to the optimal LP solution for any 0 < ε ≤ 1, where D is the largest distance constraint.
While solving linear programs in a distributed setting is interesting in its own right, this class of convex programs is particularly important because solving them is often a crucial step when designing approximation algorithms. Hence we almost immediately obtain new and improved distributed approximation algorithms for a variety of network design problems, including Basic 3- and 4-Spanner, Directed k-Spanner, Lowest Degree k-Spanner, and Shallow-Light Steiner Network Design with a spanning demand graph. Our algorithms do not require any “heavy” computation and essentially match the best-known centralized approximation algorithms, while previous approaches which do not use heavy computation give approximations which are worse than the best-known centralized bounds.
BibTeX - Entry
@InProceedings{dinitz_et_al:LIPIcs:2018:8626,
author = {Michael Dinitz and Yasamin Nazari},
title = {{Distributed Distance-Bounded Network Design Through Distributed Convex Programming}},
booktitle = {21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
pages = {5:1--5:19},
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/8626},
URN = {urn:nbn:de:0030-drops-86262},
doi = {10.4230/LIPIcs.OPODIS.2017.5},
annote = {Keywords: distributed algorithms, approximation algorithms, convex programming}
}
|
Keywords: |
|
distributed algorithms, approximation algorithms, convex programming |
|
Collection: |
|
21st International Conference on Principles of Distributed Systems (OPODIS 2017) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
28.03.2018 |
