Before revision:  Moreover , we prove that it is NP-hard to compute subsets with these characteristics, whose cardinality approximates that of the minimum cardinality subset. Additionally, we propose new algorithms for computing such subsets, with tight approximation factors in general metrics, and improved factors for doubling metrics and \ell_p metrics with p . Finally , we show an alternative implementation scheme that reduces the worst-case time complexity of one of these algorithms , becoming the first truly subquadratic approximation algorithm for the nearest-neighbor condensationproblem .
After revision:  Moreover , we prove that  . Finally , we show an alternative implementation scheme that reduces the worst-case time complexity of one of these algorithms , becoming the first truly subquadratic approximation algorithm for the nearest-neighbor condensationproblem .