Efficient distributed approximation algorithms via probabilistic tree embeddings
Maleq Khan, Fabian Kühn, Dahlia Malkhi, Gopal Pandurangan, Kunal Talwar · 2008
We present a uniform approach to design efficient distributed approximation algorithms for various network optimization problems. Our approach is randomized and based on a probabilistic tree embedding due to Fakcharoenphol, Rao, and Talwar (FRT embedding). We show how to efficiently compute an (implicit) FRT embedding in a decentralized manner and how to use the embedding to obtain expected O(log n)-approximate distributed algorithms for the generalized Steiner forest problem, the minimum routing cost spanning tree problem, and the $k$-source shortest paths problem in arbitrary networks. The time complexities of our algorithms are within a polylogarithmic factor of the optimum.