2026-08-10T07:42:41Z https://drops.dagstuhl.de/oai

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

Privacy Preserving Clustering with Constraints Rösner, Clemens Schmidt, Melanie Clustering k-center Constraints Privacy Lower Bounds Fairness The k-center problem is a classical combinatorial optimization problem which asks to find k centers such that the maximum distance of any input point in a set P to its assigned center is minimized. The problem allows for elegant 2-approximations. However, the situation becomes significantly more difficult when constraints are added to the problem. We raise the question whether general methods can be derived to turn an approximation algorithm for a clustering problem with some constraints into an approximation algorithm that respects one constraint more. Our constraint of choice is privacy: Here, we are asked to only open a center when at least l clients will be assigned to it. We show how to combine privacy with several other constraints. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Clemens Rösner and Melanie Schmidt 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.96 urn:nbn:de:0030-drops-91008 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.96 eng https://creativecommons.org/licenses/by/3.0/legalcode