Title: Estimating the weight of Euclidean minimum spanning trees in a data stream
Speaker: Christian Sohler, University of Paderborn, Germany
Date: March 8, 2004 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider the problem to compute the Euclidean minimum spanning tree of a set of n points in the R^d in the data streaming model. In this model the input point set is given sequentially, i.e. we can access the points one after the other. No random access to the input set is possible. Additionally, a streaming algorithm should use at most polylogarithmic space in the number of input points.
Since the representation of a minimum spanning tree has size Omega(n), we focus on estimating the weight of the spanning tree. We develop a streaming algorithm that computes with probability 1-delta a 1+epsilon approximation of the weight of the Euclidean minimum spanning tree. Our algorithm uses poly(log n, 1/epsilon, log 1/delta) space and requires that a rough (polynomial) approximation of the number of points in the stream is known.
Joint work with Gereon Frahling.
See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html