Approximating Fair Clustering with Cascaded Norm Objectives

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/(log log n)) 1/p )-approximation for (p, ∞)-Fair Clustering by Makarychev and Vakilian (COLT 2021).