The Library

Estimating the weight of metric minimum spanning trees in sublinear time

Tools

Czumaj, Artur and Sohler, Christian. (2009) Estimating the weight of metric minimum spanning trees in sublinear time. SIAM Journal on Computing, Vol.39 (No.3). pp. 904-922. ISSN 0097-5397

Preview

PDF
WRAP_Czumaj_estimating_weight.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (275Kb)

Official URL: http://dx.doi.org/10.1137/060672121

Abstract

In this paper we present a sublinear-time $(1+\varepsilon)$-approximation randomized algorithm to estimate the weight of the minimum spanning tree of an $n$-point metric space. The running time of the algorithm is $\widetilde{\mathcal{O}}(n/\varepsilon^{\mathcal{O}(1)})$. Since the full description of an $n$-point metric space is of size $\Theta(n^2)$, the complexity of our algorithm is sublinear with respect to the input size. Our algorithm is almost optimal as it is not possible to approximate in $o(n)$ time the weight of the minimum spanning tree to within any factor. We also show that no deterministic algorithm can achieve a $B$-approximation in $o(n^2/B^3)$ time. Furthermore, it has been previously shown that no $o(n^2)$ algorithm exists that returns a spanning tree whose weight is within a constant times the optimum.

Item Type:

Journal Article

Subjects:

Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software

Divisions:

Faculty of Science > Computer Science

Library of Congress Subject Headings (LCSH):

Spanning trees (Graph theory), Estimation theory -- Computer programs, Algorithms

Journal or Publication Title:

SIAM Journal on Computing

Publisher:

Society for Industrial and Applied Mathematics

ISSN:

0097-5397

Official Date:

26 August 2009

Dates:

Date	Event
26 August 2009	Published

Volume:

Vol.39

Number:

No.3

Page Range:

pp. 904-922

Identification Number:

10.1137/060672121

Status:

Peer Reviewed

Access rights to Published version:

Open Access

References:

[1] N. Alon, S. Dar, M. Parnas, and D. Ron, Testing of clustering, SIAM J. Discrete Math.,
16 (2003), pp. 393–417.
[2] T. Batu, F. Erg¨un, J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld, and R. Sami,
A sublinear algorithm for weakly approximating edit distance, in Proceedings of the 35th
Annual ACM Symposium on Theory of Computing (STOC), 2003, pp. 316–324.
[3] P. Berenbrink, F. Erg¨un, and T. Friedetzky, Finding frequent patterns in a string in
sublinear time, in Proceedings of the 13th Annual European Symposium on Algorithms
(ESA), Springer-Verlag, Berlin, 2005, pp. 746–757.
[4] P. B. Callahan and S. R. Kosaraju, A decomposition of multidimensional point sets with
applications to k-nearest-neighbors and n-body potential fields, J. ACM, 42 (1995), pp.
67–90.
[5] B. Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity,
J. ACM, 47 (2000), pp. 1012–1027.
[6] B. Chazelle, D. Liu, and A. Magen, Sublinear geometric algorithms, SIAM J. Comput., 35
(2006), pp. 627–646.
[7] B. Chazelle, R. Rubinfeld, and L. Trevisan, Approximating the minimum spanning tree
weight in sublinear time, SIAM J. Comput., 34 (2005), pp. 1370–1379.
[8] A. Czumaj, F. Erg¨un, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, and C. Sohler,
Approximating the weight of the Euclidean minimum spanning tree in sublinear time,
SIAM J. Comput., 35 (2005), pp. 91–109.
[9] A. Czumaj and C. Sohler, Sublinear-time algorithms, Bull. Eur. Assoc. Theor. Comput. Sci.
EATCS, 89 (2006), pp. 23–47.
[10] D. Eppstein, Spanning trees and spanners, in Handbook of Computational Geometry, J.-R.
Sack and J. Urrutia, eds., North–Holland, Amsterdam, 2000, pp. 425–461.
[11] F. Erg¨un, S. Muthukrishnan, and C. Sahinalp, Sublinear methods for detecting periodic
trends in data streams, in Proceedings of the 6th Latin American Symposium on Theoretical
Informatics (LATIN), Springer-Verlag, Berlin, 2004, pp. 16–28.
[12] A. Frieze and R. Kannan, The regularity lemma and approximation schemes for dense problems,
in Proceedings of the 37th IEEE Symposium on Foundations of Computer Science
(FOCS), 1996, pp. 12–20.
[13] A. Frieze, R. Kannan, and S. Vempala, Fast Monte-Carlo algorithms for finding low-rank
approximations, J. ACM, 51 (2004), pp. 1025–1041.
[14] O. Goldreich, S. Goldwasser, and D. Ron, Property testing and its connection to learning
and approximation, J. ACM, 45 (1998), pp. 653–750.
[15] O. Goldreich and D. Ron, Approximating average parameters of graphs, in Proceedings of the
10th International Workshop on Randomization and Computation (RANDOM), Springer-
Verlag, Berlin, Heidelberg, 2006, pp. 363–374.
[16] A. Hajnal and E. Szemer´edi, Proof of a conjecture of P. Erd˝os, in Combinatorial Theory and
Its Applications, Vol. 2, P. Erd˝os, A. R´enyi, and V. T. S´os, eds., North–Holland, London,
1970, pp. 601–623.
[17] P. Indyk, A sublinear time approximation scheme for clustering in metric spaces, in Proceedings
of the 39th IEEE Symposium on Foundations of Computer Science (FOCS), 1998, pp.
154–159.
[18] P. Indyk, Sublinear time algorithms for metric space problems, in Proceedings of the 31st
Annual ACM Symposium on Theory of Computing (STOC), 1999, pp. 428–434.
[19] D. R. Karger, P. N. Klein, and R. E. Tarjan, A randomized linear-time algorithm to find
minimum spanning trees, J. ACM, 42 (1995), pp. 321–328.
[20] N. Mishra, D. Oblinger, and L. Pitt, Sublinear time approximate clustering, in Proceedings
of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2001, pp.
439–447.
[21] M. Parnas and D. Ron, Approximating the minimum vertex cover in sublinear time and a
connection to distributed algorithms, Theoret. Comput. Sci., 381 (2007), pp. 183–196.
[22] S. Pettie and V. Ramachandran, An optimal minimum spanning tree algorithm, J. ACM,
49 (2002), pp. 16–34.
[23] V. V. Vazirani, Approximation Algorithms, Springer-Verlag, Berlin, 2001.
[24] A. C.-C. Yao, On constructing minimum spanning trees in k-dimensional spaces and related
problems, SIAM J. Comput., 11 (1982), pp. 721–736.