2026-07-26T19:17:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20640 2024-08-23T05:50:30Z ddc:004 open_access

Faster Approximation Schemes for (Constrained) k-Means with Outliers Zhang, Zhen Huang, Junyu Feng, Qilong Approximation algorithms clustering Given a set of n points in ℝ^d and two positive integers k and m, the Euclidean k-means with outliers problem aims to remove at most m points, referred to as outliers, and minimize the k-means cost function for the remaining points. Developing algorithms for this problem remains an active area of research due to its prevalence in applications involving noisy data. In this paper, we give a (1+ε)-approximation algorithm that runs in n²d((k+m)ε^{-1})^O(kε^{-1}) time for the problem. When combined with a coreset construction method, the running time of the algorithm can be improved to be linear in n. For the case where k is a constant, this represents the first polynomial-time approximation scheme for the problem: Existing algorithms with the same approximation guarantee run in polynomial time only when both k and m are constants. Furthermore, our approach generalizes to variants of k-means with outliers incorporating additional constraints on instances, such as those related to capacities and fairness. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zhen Zhang and Junyu Huang and Qilong Feng 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.84 urn:nbn:de:0030-drops-206408 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.84 eng https://creativecommons.org/licenses/by/4.0/legalcode