2026-10-11T13:49:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8626 2024-03-06T09:42:11Z ddc:004 open_access

Distributed Distance-Bounded Network Design Through Distributed Convex Programming Dinitz, Michael Nazari, Yasamin distributed algorithms approximation algorithms convex programming 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Dinitz and Yasamin Nazari 2018 Is Part Of LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2017.5 urn:nbn:de:0030-drops-86262 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.5 eng https://creativecommons.org/licenses/by/3.0/legalcode