Privacy preserving clustering with constraints

By Clemens Rösner, Melanie Schmidt. 2018

122 citations recorded by the source corpus.

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 $\ell$ clients will be assigned to it. We show how to combine privacy with several other constraints.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Organizational Behavior and Human Resource Management

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Organizational Behavior and Human Resource Management

Citations in the corpus

Proportionally Fair Clustering (2019, background): “In [9] and subsequent generalizations [31, 4], the authors consider fair clustering in terms of balance: There are red and blue points, and a balanced solution has roughly the same ratio of blue to red points in every cluster as in the overall population.”
Scalable Fair Clustering (2019, background): “The work most relevant to our paper is a recent manuscript by Schmidt et al. (2018), which proposed eﬃcient streaming algorithms for fair k -means (which is similar to k -median studied here).”
Fairness in Machine Learning: A Survey (2020, unknown): “[243, 64, 22, 232, 14, 23, 22, 61]); 2) investigating the presence and detection of discrimination in association rule mining (e.”
Fair Algorithms for Clustering (2019, methodology): “in [25] first addresses disparate impact for clustering problems in the presence of two groups, Rösner and Schmidt [60] generalizes it to more than two groups.”
On the cost of essentially fair clusterings (2018, methodology): “Rösner and Schmidt [34] showed that case 2 with two colors and balance ( P ) = 1 /t for an integer t can be generalized to an arbitrary number of colors with | col i ( P ) | | col 0 ( P ) ∈ N for all 1 ≤ i ≤ g .”
Rényi Fair Inference (2019, methodology): “Many recent works on fair clustering propose a two-phase algorithm for solving the K-centers and K-median fair clustering problems [13, 5, 43, 7].”
Fair Coresets and Streaming Algorithms for Fair k-Means Clustering (2018, background): “Rösner and Schmidt [42] extend their deﬁnition to multiple colors and develop an approximation algorithm for k -center.”