Back to Search
Start Over
Approximating All-Points Furthest Pairs and Maximum Spanning Trees in Metric Spaces.
- Source :
-
International Journal of Foundations of Computer Science . Aug2024, Vol. 35 Issue 5, p595-603. 9p. - Publication Year :
- 2024
-
Abstract
- Consider the problem of finding a point furthest from x for each point x in a metric space ([ n ] , d) , where [ n ] = { 1 , 2 , ... , n }. We prove this problem to have a deterministic O (n) -time 1 / 3 -approximation algorithm. As a corollary, the maximum spanning tree problem in metric spaces has a deterministic O (n) -time 1 / 3 -approximation algorithm. We also give a Monte Carlo O (n 1. 5 log n) -time algorithm outputting, for each x ∈ [ n ] , a point y x ∈ [ n ] satisfying d (x , y x) ≥ Δ / 2 , where Δ ≡ max x , y ∈ [ n ] d (x , y). As a corollary, we have a Monte Carlo O (n 1. 5 log n) -time algorithm for finding a spanning tree of weight at least (1 / 2 − o (1)) Δ n in ([ n ] , d). [ABSTRACT FROM AUTHOR]
- Subjects :
- *COMMERCIAL space ventures
*METRIC spaces
*SPANNING trees
Subjects
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 35
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 178313981
- Full Text :
- https://doi.org/10.1142/S0129054123500181