Title : Efficient Distributed Approximation Algorithms for Minimum Spanning Trees
Speaker : Gopal Pandurangan, Department of Computer Science, Purdue University
When : 4:30-5:30pm May 3rd
Where : PPB 300
ABSTRACT : The Minimum Spanning Tree (MST) problem is one of the most important and commonly occurring primitive in the design and operation of data and communication networks. There are almost optimal distributed algorithms for this problem. However, these algorithms require relatively large amount of communication or time, and are fairly involved; this makes these algorithms impractical for emerging technologies such as peer-to-peer and sensor networks. The focus of this talk is a very simple scheme called the Nearest Neighbor Tree (NNT) scheme for constructing an O(log n)-approximate MST in a weighted graph. We use the scheme to design efficient distributed approximation algorithms for the MST problem under various settings:
(1) A randomized variant of the scheme can be applied to design a communication-efficient distributed approximation algorithm in a complete weighted metric network. Our result shows that the expected communication complexity of our algorithm is significantly better than the best distributed algorithm that finds the MST.
(2) We show that our scheme can be used to construct a fast distributed MST approximation algorithm in arbitrary networks. Our algorithm is existentially optimal (up to polylogarithmic factors) with respect to both time and communication complexity. Significantly, our result also shows that there can be an exponential time gap between exact and approximate MST computation. Another consequence of our result is that an approximate MST in unit-disk graphs (which are popular models of wireless networks) and in random weighted networks can be found in almost optimal time.
(3) Our scheme can also be used in ad hoc wireless networks to construct low-energy spanning trees in a energy-efficient manner. For uniform distribution of nodes, we show that our algorithms give a constant approximation; we also show that the energy needed to construct these approximate spanning trees is within a constant factor of the minimum possible energy that is needed to construct the optimal energy tree. The time and communication complexities of our algorithms are nearly the best possible.
(Joint works with Maleq Khan and V.S. Anil Kumar.)
