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
Abstract:
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)