Title: Nearest Neighbor Trees and their Algorithmic Applications
Speaker: Gopal Pandurangan, Purdue University
Date: February 15, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
There are almost optimal sequential and distributed algorithms for the Minimum Spanning Tree (MST) problem. However, these algorithms require relatively large number of messages, and relatively large amount of time, and are fairly involved, require synchronization and a lot of book keeping; this makes these algorithms impractical for emerging technologies such as ad hoc and sensor networks. The central theme of this talk is a family of extremely simple, local algorithms that have very low message complexity, but produce a {\em logarithmic} approximation to the {\em Metric} MST problem. We call these algorithms the {\em Nearest Neighbor Tree (NNT) algorithms}, and these employ a very simple idea to eliminate the work involved in cycle detection in other MST algorithms: each node chooses a distinct rank, and connects to the closest node of higher rank.
We prove several interesting properties and applications of NNT algorithms. We show that for any metric instance, any NNT algorithm gives an $O(\log{n})$ approximation to the MST. By varying the process of choosing the ranks, we define Random-NNT, in which each node chooses a rank randomly from some space, and Directional-NNT, in which each node uses the coordinate information to define ranks. In the point-to- point distributed model, in which the processors are connected in a clique, we show that the Random-NNT algorithm can be implemented in $O(\log{n})$ time and expected $O(n\log{n})$ messages, contrasting the $\Omega(n^2)$ deterministic lower bound for finding the optimal MST by Korach et al. For geometric instances, we show that Random-NNT constructs low-degree spanning trees which have $O(\log{n})$ maximum degree, with high probability, using significantly less work than the worst-case lower bound. Finally, we show that NNT algorithms can also be adapted fairly easily to yield simple fast fully-dynamic algorithms for maintaining an approximate MST.