Abstract
The 1center clustering with outliers problem asks about identifying a prototypical robust statistic that approximates the location of a cluster of points. Given some constant 0 < alpha < 1 and n points such that alpha 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 alpha n points. This problem can be formulated with the points in a normed vector space such as R^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 L^p vector space, we show an O(nd)time solution with a ball of radius O(r) for a fixed alpha > 1/2, and for any normed vector space, we show an O(nd)time solution with a ball of radius O(r) when alpha > 1/2 as well as an O(nd log^{(k)}(n))time solution with a ball of radius O(r) for all alpha > 0, k in N, 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 in N an O(n^{1+1/C})time solution that finds a ball of radius 2Cr, assuming distance computation between any pair of points takes O(1)time, and show that for any alpha, C, an O(n^{1+1/C})time solution that finds a ball of radius ((2C3)(1alpha)1)r cannot exist.
BibTeX  Entry
@InProceedings{narayanan:LIPIcs:2018:9425,
author = {Shyam Narayanan},
title = {{Deterministic O(1)Approximation Algorithms to 1Center Clustering with Outliers}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {21:121:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9425},
URN = {urn:nbn:de:0030drops94253},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.21},
annote = {Keywords: Deterministic, Approximation Algorithm, Cluster, Statistic}
}
Keywords: 

Deterministic, Approximation Algorithm, Cluster, Statistic 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) 
Issue Date: 

2018 
Date of publication: 

13.08.2018 