Approximating All-Points Furthest Pairs and Maximum Spanning Trees in Metric Spaces.

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]