Distributed distance-bounded network design through distributed convex programming

DOI10.4230/LIPICS.OPODIS.2017.5MaRDI QIDQ3300803zbMATH OpenOpenAlexFDO

Authors Michael Dinitz, Yasamin Nazari

Publication date 30 July 2020

Full work available at URL https://arxiv.org/abs/1703.07417

zbMATH Keywords

approximation algorithmsconvex programmingdistributed algorithms

Mathematics Subject Classification ID

Convex programming (90C25) Approximation algorithms (68W25) Distributed algorithms (68W15) Network design and communication in computer systems (68M10)

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/epsilon)logn)$ rounds in the $mathcalLOCAL$ model and finds a $(1+epsilon)$-approximation to the optimal LP solution for any $0<epsilonleq1$, 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.

Recommendations

• Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control
• Stateless distributed gradient descent for positive linear programs
• Distributed Spanner Approximation
• Distributed spanner approximation
• Local approximability of max-min and min-max linear programs

Cites work

• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Design networks with bounded pairwise distance
• Directed spanners via flow-based linear programs
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Strong Diameter Network Decomposition
• Fault-tolerant spanners
• Geometric algorithms and combinatorial optimization
• Graph spanners
• Improved approximation for the directed spanner problem
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
• Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
• Linear programming without the matrix
• Local approximability of max-min and min-max linear programs
• Low diameter graph decompositions
• Lowest-degree k-spanner: approximation and hardness
• Oblivious network design
• The price of being near-sighted

Cited in

(2)

• Distributed spanner approximation
• Stateless distributed gradient descent for positive linear programs

This page was built for publication: Distributed distance-bounded network design through distributed convex programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3300803)