### DIMACS Theoretical Computer Science Seminar

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.