On coresets for fair clustering in metric and Euclidean spaces and their applications
From MaRDI portal
Publication:6152182
Abstract: Fair clustering is a constrained variant of clustering where the goal is to partition a set of colored points, such that the fraction of points of any color in every cluster is more or less equal to the fraction of points of this color in the dataset. This variant was recently introduced by Chierichetti et al. [NeurIPS, 2017] in a seminal work and became widely popular in the clustering literature. In this paper, we propose a new construction of coresets for fair clustering based on random sampling. The new construction allows us to obtain the first coreset for fair clustering in general metric spaces. For Euclidean spaces, we obtain the first coreset whose size does not depend exponentially on the dimension. Our coreset results solve open questions proposed by Schmidt et al. [WAOA, 2019] and Huang et al. [NeurIPS, 2019]. The new coreset construction helps to design several new approximation and streaming algorithms. In particular, we obtain the first true constant-approximation algorithm for metric fair clustering, whose running time is fixed-parameter tractable (FPT). In the Euclidean case, we derive the first -approximation algorithm for fair clustering whose time complexity is near-linear and does not depend exponentially on the dimension of the space. Besides, our coreset construction scheme is fairly general and gives rise to coresets for a wide range of constrained clustering problems. This leads to improved constant-approximations for these problems in general metrics and near-linear time -approximations in the Euclidean metric.
Recommendations
- Fair coresets and streaming algorithms for fair \(k\)-means
- Fair colorful \(k\)-center clustering
- Fair colorful k-center clustering
- On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
- New algorithms for fair \(k\)-center problem with outliers and capacity constraints
Cites work
- A constant-factor approximation algorithm for the k-median problem
- A new coreset framework for clustering
- A unified framework for approximating and clustering data
- A unified framework for clustering constrained data without locality property
- An application of simultaneous diophantine approximation in combinatorial optimization
- An approximation algorithm for uniform capacitated k-median problem with 1+ capacity violation
- Approximating k-median with non-uniform capacities
- Approximating extent measures of points.
- Approximation Schemes for Capacitated Clustering in Doubling Metrics
- Bi-factor approximation algorithms for hard capacitated k-median problems
- Centrality of trees for capacitated \(k\)-center
- Clustering to minimize the maximum intercluster distance
- Clustering with diversity
- Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
- Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal
- Coresets in dynamic geometric data streams
- Decomposable searching problems I. Static-to-dynamic transformation
- Degree bounded matroids and submodular flows
- Dimensionality reduction for k-means clustering and low rank approximation
- Fair coresets and streaming algorithms for fair \(k\)-means
- Fairness through awareness
- Faster algorithms for the constrained k-means problem
- Fault tolerant \(K\)-center problems
- How to Allocate Network Centers
- Improved Algorithms for Bipartite Network Flow
- Improved approximation guarantees for lower-bounded facility location
- Improved PTAS for the constrained \(k\)-means problem
- Integer Programming with a Fixed Number of Variables
- Lower-bounded facility location
- Minkowski's Convex Body Theorem and Integer Programming
- Oblivious dimension reduction for \(k\)-means: beyond subspaces and the Johnson-Lindenstrauss lemma
- On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
- On coresets for k-means and k-median clustering
- On uniform capacitated k-median beyond the natural LP relaxation
- On uniform capacitated \(k\)-median beyond the natural LP relaxation
- Privacy preserving clustering with constraints
- Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
- Smaller coresets for k-median and k-means clustering
- StreamKM++, a clustering algorithm for data streams
- Sublinear time algorithms for metric space problems
- The Capacitated K-Center Problem
- Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
- Universal \({\epsilon}\)-approximators for integrals
Cited in
(4)
This page was built for publication: On coresets for fair clustering in metric and Euclidean spaces and their applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6152182)
