Yasamin Nazari
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/ϵ)logn) rounds in
the LOCAL model and 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.
Joint work with Michael Dinitz.