Dinitz, Michael ;
Nazari, Yasamin
Distributed DistanceBounded 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 “distancebounded 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 4Spanner, Directed kSpanner, Lowest Degree kSpanner, and ShallowLight Steiner Network Design with a spanning demand graph. Our algorithms do not require any “heavy” computation and essentially match the bestknown centralized approximation algorithms, while previous approaches which do not use heavy computation give approximations which are worse than the bestknown centralized bounds.
BibTeX  Entry
@InProceedings{dinitz_et_al:LIPIcs:2018:8626,
author = {Michael Dinitz and Yasamin Nazari},
title = {{Distributed DistanceBounded Network Design Through Distributed Convex Programming}},
booktitle = {21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
pages = {5:15:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770613},
ISSN = {18688969},
year = {2018},
volume = {95},
editor = {James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8626},
URN = {urn:nbn:de:0030drops86262},
doi = {10.4230/LIPIcs.OPODIS.2017.5},
annote = {Keywords: distributed algorithms, approximation algorithms, convex programming}
}
28.03.2018
Keywords: 

distributed algorithms, approximation algorithms, convex programming 
Seminar: 

21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Issue date: 

2018 
Date of publication: 

28.03.2018 