Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers

The 1-center clustering with outliers problem asks about identifying a prototypical robust statistic that approximates the location of a cluster of points. Given some constant 0 < α < 1 and n points such that α n of them are in some (unknown) ball of radius r, the goal is to compute a ball of radius O(r) that also contains α n points. This problem can be formulated with the points in a normed vector space such as ℝd or in a general metric space. The problem has a simple randomized solution: a randomly selected point is a correct solution with constant probability, and its correctness can be verified in linear time. However, the deterministic complexity of this problem was not known. In this paper, for any ℓp vector space, we show an O(nd)-time solution with a ball of radius O(r) for a fixed α > frac12, and for any normed vector space, we show an O(nd)-time solution with a ball of radius O(r) when α > frac12 as well as an O (nd log(k)(n))-time solution with a ball of radius O(r) for all α > 0, k ∈ mathbbN, where log(k)(n) represents the kth iterated logarithm, assuming distance computation and vector space operations take O(d) time. For an arbitrary metric space, we show for any C ∈ mathbbN an O(n1+1/C)-time solution that finds a ball of radius 2Cr, assuming distance computation between any pair of points takes O(1)-time. Moreover, this algorithm is optimal for general metric spaces, as we show that for any fixed α, C, there is no o(n1+1/C)-query and thus no o(n1+1/C)-time solution that deterministically finds a ball of radius 2Cr.