2026-07-24T06:31:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13652 2024-03-06T10:52:34Z ddc:004 open_access

Achieving Anonymity via Weak Lower Bound Constraints for k-Median and k-Means Arutyunova, Anna Schmidt, Melanie Clustering with Constraints lower Bounds k-Means Anonymity We study k-clustering problems with lower bounds, including k-median and k-means clustering with lower bounds. In addition to the point set P and the number of centers k, a k-clustering problem with (uniform) lower bounds gets a number B. The solution space is restricted to clusterings where every cluster has at least B points. We demonstrate how to approximate k-median with lower bounds via a reduction to facility location with lower bounds, for which O(1)-approximation algorithms are known. Then we propose a new constrained clustering problem with lower bounds where we allow points to be assigned multiple times (to different centers). This means that for every point, the clustering specifies a set of centers to which it is assigned. We call this clustering with weak lower bounds. We give an 8-approximation for k-median clustering with weak lower bounds and an O(1)-approximation for k-means with weak lower bounds. We conclude by showing that at a constant increase in the approximation factor, we can restrict the number of assignments of every point to 2 (or, if we allow fractional assignments, to 1+ε). This also leads to the first bicritera approximation algorithm for k-means with (standard) lower bounds where bicriteria is interpreted in the sense that the lower bounds are violated by a constant factor. All algorithms in this paper run in time that is polynomial in n and k (and d for the Euclidean variants considered). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anna Arutyunova and Melanie Schmidt 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.7 urn:nbn:de:0030-drops-136529 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.7 eng https://creativecommons.org/licenses/by/4.0/legalcode