Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings

Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, and Kunal Talwar


We present a uniform approach to design efficient distributed approximation algorithms for various fundamental network optimization problems. Our approach is randomized and based on a probabilistic tree embedding due to Fakcharoenphol, Rao, and Talwar [16] (FRT embedding). We show how to efficiently compute an (implicit) FRT embedding in a decentralized manner and how to use the embedding to obtain efficient expected O(log n)-approximate distributed algorithms for various problems, in particular the generalized Steiner forest problem (including the minimum Steiner tree problem), the minimum routing cost spanning tree problem, and the k-source shortest paths problem. The distributed construction of the FRT embedding is based on the computation of least elements (LE) lists, a distributed data structure that is of independent interest. Assuming a global order on the nodes of a network, the LE-list of a node stores the smallest node (w.r.t. the given order) within every distance d (cf. Cohen [8], Cohen and Kaplan [9]). Assuming a random order on the nodes, we give a distributed algorithm for computing LE-lists on a weighted graph with time complexity O(S log n), where S is a graph parameter called the shortest path diameter which can be considered the weighted counterpart of the diameter D of the graph. For unweighted graphs, our LE-lists computation has asymptotically optimal time complexity of O(D). As a byproduct, we get an improved synchronous leader election algorithm for general networks that is both time-optimal and almost message-optimal with high probability.


Publication typeArticle
Published inDistributed Computing
> Publications > Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings