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)

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
Date:	26 August 2009
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.
URI:	http://wrap.warwick.ac.uk/id/eprint/2416

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item