Tight FPT approximation for socially fair clustering

DOI10.1016/j.ipl.2023.106383arXiv2106.06755OpenAlexW4321486958MaRDI QIDQ6161442

Dishant Goyal, Ragesh Jaiswal

Publication date: 5 June 2023

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

fairnessclusteringapproximation algorithmsfixed-parameter tractability\(k\)-means

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Efficient algorithms for fair clustering with a new notion of fairness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Faster algorithms for the constrained \(k\)-means problem
• A unified framework for clustering constrained data without locality property
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• Least squares quantization in PCM
• A Constant Factor Approximation Algorithm for Fault-Tolerant k -Median
• On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
• On the Parameterized Complexity of Approximating Dominating Set
• Constant approximation for k-median and k-means with outliers via iterative rounding
• Parameterized Algorithms
• On the cost of essentially fair clusterings
• A new coreset framework for clustering
• FPT Approximation for Constrained Metric k-Median/Means