2021/11/08 by Eden Chlamtáč, Chlamtáč, Eden, Yury Makarychev +3 · 4 citations
Business, Management and Accounting · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2111.04804
openalex publication_date 2021/11/08 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
We introduce the (p,q)-Fair Clustering problem. In this problem, we are given a set of points P and a collection of different weight functions W. We would like to find a clustering which minimizes the ℓq-norm of the vector over W of the ℓp-norms of the weighted distances of points in P from the centers. This generalizes various clustering problems, including Socially Fair k-Median and k-Means, and is closely connected to other problems such as Densest k-Subgraph and Min k-Union. We utilize convex programming techniques to approximate the (p,q)-Fair Clustering problem for different values of p and q. When p≥ q, we get an O(k(p-q)/(2pq)), which nearly matches a kΩ((p-q)/(pq)) lower bound based on conjectured hardness of Min k-Union and other problems. When q≥ p, we get an approximation which is independent of the size of the input for bounded p,q, and also matches the recent O((log n/(loglog n))1/p)-approximation for (p, ∞)-Fair Clustering by Makarychev and Vakilian (COLT 2021).