2026-07-25T03:00:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9425 2024-03-06T10:44:22Z ddc:004 open_access

Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers Narayanan, Shyam Deterministic Approximation Algorithm Cluster Statistic 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 < 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 ((2C-3)(1-alpha)-1)r cannot exist. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shyam Narayanan 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.21 urn:nbn:de:0030-drops-94253 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.21 eng https://creativecommons.org/licenses/by/3.0/legalcode