License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.7
URN: urn:nbn:de:0030-drops-136529
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13652/
Go to the corresponding LIPIcs Volume Portal

Arutyunova, Anna ; Schmidt, Melanie

Achieving Anonymity via Weak Lower Bound Constraints for k-Median and k-Means

pdf-format:
LIPIcs-STACS-2021-7.pdf (0.7 MB)

Abstract

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).

BibTeX - Entry

@InProceedings{arutyunova_et_al:LIPIcs.STACS.2021.7,
  author =	{Arutyunova, Anna and Schmidt, Melanie},
  title =	{{Achieving Anonymity via Weak Lower Bound Constraints for k-Median and k-Means}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13652},
  URN =		{urn:nbn:de:0030-drops-136529},
  doi =		{10.4230/LIPIcs.STACS.2021.7},
  annote =	{Keywords: Clustering with Constraints, lower Bounds, k-Means, Anonymity}
}

Keywords: Clustering with Constraints, lower Bounds, k-Means, Anonymity
Collection: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue Date: 2021
Date of publication: 10.03.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI