On coresets for fair clustering in metric and Euclidean spaces and their applications

DOI10.1016/j.jcss.2024.103506arXiv2007.10137OpenAlexW3042622391MaRDI QIDQ6152182

Fedor V. Fomin, Kirill Simonov, Sayan Bandyapadhyay

Publication date: 11 March 2024

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2007.10137

zbMATH Keywords

approximation algorithmscoresetsfair clustering

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matroid and knapsack center problems
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• Centrality of trees for capacitated \(k\)-center
• Clustering to minimize the maximum intercluster distance
• An application of simultaneous diophantine approximation in combinatorial optimization
• Fault tolerant \(K\)-center problems
• Faster algorithms for the constrained \(k\)-means problem
• A constant-factor approximation algorithm for the \(k\)-median problem
• Fair coresets and streaming algorithms for fair \(k\)-means
• A unified framework for clustering constrained data without locality property
• Improved PTAS for the constrained \(k\)-means problem
• Degree bounded matroids and submodular flows
• Sublinear time algorithms for metric space problems
• Fairness through awareness
• Improved Approximation Guarantees for Lower-Bounded Facility Location
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems
• Integer Programming with a Fixed Number of Variables
• Approximating extent measures of points
• An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• 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
• Coresets in dynamic geometric data streams
• Clustering with Diversity
• Minkowski's Convex Body Theorem and Integer Programming
• Decomposable searching problems I. Static-to-dynamic transformation
• How to Allocate Network Centers
• Improved Algorithms for Bipartite Network Flow
• The Capacitated K-Center Problem
• On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
• Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal
• Approximation Schemes for Capacitated Clustering in Doubling Metrics
• Oblivious dimension reduction for k -means: beyond subspaces and the Johnson-Lindenstrauss lemma
• On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
• Bi-Factor Approximation Algorithms for Hard Capacitated k-Median Problems
• StreamKM++
• A unified framework for approximating and clustering data
• A new coreset framework for clustering

This page was built for publication: On coresets for fair clustering in metric and Euclidean spaces and their applications