DIMACS Theoretical Computer Science Seminar

Title: Estimating the weight of metric minimum spanning trees in sublinear-time

Speaker: Artur Czumaj, NJIT

Date: October 27, 2003 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ


In this talk, we'll present a sublinear time randomized algorithm to
estimate the weight of the minimum spanning tree of an n point metric
space within a factor of 1+epsilon. For any positive constant epsilon, the
running time of the algorithm is O(n poly-log(n)), which is sublinear in
the full description size of the input, which is n^2.
It has been previously shown that no o(n^2) algorithm exists that returns
a spanning tree whose weight is a constant times the optimum. Our
algorithm is almost optimal as it is not possible to approximate in o(n)
the weight of the minimum spanning tree within any factor.

(Joint work with Christian Sohler, U. Paderborn)