ESTIMATING THE WEIGHT OF METRIC MINIMUM SPANNING TREES IN SUBLINEAR TIME

被引：36

作者：

Czumaj, Artur ^{[1
,2
]}

Sohler, Christian ^{[3
]}

机构：

[1] Univ Warwick, Dept Comp Sci, Coventry CV4 7AL, W Midlands, England

[2] Univ Warwick, Ctr Discrete Math & Applicat, Coventry CV4 7AL, W Midlands, England

[3] Tech Univ Dortmund, Dept Comp Sci, D-44221 Dortmund, Germany

来源：

SIAM JOURNAL ON COMPUTING | 2009年 / 39卷 / 03期

基金：

英国工程与自然科学研究理事会;

关键词：

randomized algorithms; approximation algorithms; sublinear-time algorithms; CONNECTION;

D O I：

10.1137/060672121

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we present a sublinear-time (1 + epsilon)-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 (O) over tilde (n/epsilon(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.

引用

页码：904 / 922

页数：19

共 24 条

[1] Testing of clustering [J].

Alon, N ;

Dar, S ;

Parnas, M ;

Ron, D .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2003, 16 (03) :393-417

[2]

[Anonymous], 2001, Approximation algorithms

[3]

Batu T., 2003, P 35 ANN ACM S THEOR, V35, P316, DOI [DOI 10.1145/780542.780590, 10.1145/780542.780590]

[4]

Berenbrink P, 2005, LECT NOTES COMPUT SC, V3669, P746

[5] A DECOMPOSITION OF MULTIDIMENSIONAL POINT SETS WITH APPLICATIONS TO K-NEAREST-NEIGHBORS AND N-BODY POTENTIAL FIELDS [J].

CALLAHAN, PB ;

KOSARAJU, SR .

JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 1995, 42 (01) :67-90

[6] Sublinear geometric algorithms [J].

Chazelle, B ;

Liu, D ;

Magen, A .

SIAM JOURNAL ON COMPUTING, 2006, 35 (03) :627-646

[7] Approximating the minimum spanning tree weight in sublinear time [J].

Chazelle, B ;

Rubinfeld, R ;

Trevisan, L .

SIAM JOURNAL ON COMPUTING, 2005, 34 (06) :1370-1379

[8] The soft heap: An approximate priority queue with optimal error rate [J].

Chazelle, B .

JOURNAL OF THE ACM, 2000, 47 (06) :1012-1027

[9] Approximating the weight of the Euclidean minimum spanning tree in sublinear time [J].

Czumaj, A ;

Ergün, F ;

Fortnow, L ;

Magen, A ;

Newman, I ;

Rubinfeld, R ;

Sohler, C .

SIAM JOURNAL ON COMPUTING, 2005, 35 (01) :91-109

[10]

Eppstein D, 2000, HANDBOOK OF COMPUTATIONAL GEOMETRY, P425, DOI 10.1016/B978-044482537-7/50010-3

← 1 2 3 →