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. 904922. ISSN 00975397

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 sublineartime $(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:  00975397 
Date:  26 August 2009 
Volume:  Vol.39 
Number:  No.3 
Page Range:  pp. 904922 
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), SpringerVerlag, Berlin, 2005, pp. 746–757. [4] P. B. Callahan and S. R. Kosaraju, A decomposition of multidimensional point sets with applications to knearestneighbors and nbody potential fields, J. ACM, 42 (1995), pp. 67–90. [5] B. Chazelle, A minimum spanning tree algorithm with inverseAckermann 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, Sublineartime 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), SpringerVerlag, 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 MonteCarlo algorithms for finding lowrank 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 lineartime 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 ACMSIAM 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, SpringerVerlag, Berlin, 2001. [24] A. C.C. Yao, On constructing minimum spanning trees in kdimensional spaces and related problems, SIAM J. Comput., 11 (1982), pp. 721–736. 
URI:  http://wrap.warwick.ac.uk/id/eprint/2416 
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
View Item 