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

ABSTRACT

In this paper we present a sublinear time (1 + ε)-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 Û(n/ε^O(1)). Since the full description of an n-point metric space is of size Θ(n²), 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. Furthermore, it has been previously shown that no o(n²) algorithm exists that returns a spanning tree whose weight is within a constant times the optimum.

REFERENCES

• 1: N. Alon , S. Dar , M. Parnas , D. Ron, Testing of clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.240, November 12-14, 2000
• 2: Tugkan Batu , Funda Ergün , Joe Kilian , Avner Magen , Sofya Raskhodnikova , Ronitt Rubinfeld , Rahul Sami, A sublinear algorithm for weakly approximating edit distance, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780590]
• 3: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995 [doi>10.1145/200836.200853]
• 4: Bernard Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the ACM (JACM), v.47 n.6, p.1028-1047, Nov. 2000 [doi>10.1145/355541.355562]
• 5: Bernard Chazelle , Ding Liu , Avner Magen, Sublinear geometric algorithms, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780620]
• 6: Bernard Chazelle , Ronitt Rubinfeld , Luca Trevisan, Approximating the Minimum Spanning Tree Weight in Sublinear Time, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.190-200, July 08-12, 2001
• 7: Artur Czumaj , Funda Ergün , Lance Fortnow , Avner Magen , Ilan Newman , Ronitt Rubinfeld , Christian Sohler, Sublinear-time approximation of Euclidean minimum spanning tree, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 8: Artur Czumaj , Christian Sohler , Martin Ziegler, Property Testing in Computational Geometry, Proceedings of the 8th Annual European Symposium on Algorithms, p.155-166, September 05-08, 2000
• 9: D. Eppstein. Spanning trees and spanners. In J. -R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, chapter 9, pages 425--461. Elsevier Science B. V., 1997.
• 10: A. Frieze, The regularity lemma and approximation schemes for dense problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.12, October 14-16, 1996
• 11: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
• 12: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 13: Piotr Indyk, A Sublinear Time Approximation Scheme for Clustering in Metric Spaces, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.154, October 17-18, 1999
• 14: Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301366]
• 15: David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
• 16: Nina Mishra , Dan Oblinger , Leonard Pitt, Sublinear time approximate clustering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.439-447, January 07-09, 2001, Washington, D.C., United States
• 17: Seth Pettie , Vijaya Ramachandran, An optimal minimum spanning tree algorithm, Journal of the ACM (JACM), v.49 n.1, p.16-34, January 2002 [doi>10.1145/505241.505243]
• 18: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 19: A. C. Yao. On Constructing minimum spanning trees in $k$-demensional spaces and related problems. SIAM Journal on Computing, 11: 721--736, 1982.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
approximations algorithms, minimum spanning tree, randomized algorithms, sublinear-time algorithms