Source-linked AI summary
Socially Fair Clustering: Parameterized Approximation and Local Search
Aditya Anand, Yury Makarychev, Liren Shan
TL;DR
The paper addresses open questions in socially fair clustering, including a constant-factor FPT approximation parameterized only by the number of groups. It develops parameterized center-closing methods and analyzes a simpler local-search approach for (p,q)-Clustering, obtaining an O(q)-approximation with explicit efficiency guarantees.
Problem
Fair clustering seeks solutions that maintain good quality across groups, while a constant-factor FPT algorithm parameterized solely by the number of groups had remained open.
Method
The paper combines a parameterized procedure for closing additional centers with profile-based reassignment analysis and a derivative-based local-search analysis for (p,q)-Clustering.
Results
The paper gives a constant-factor FPT approximation for ℓp-Clustering parameterized by ℓ and an O(q)-approximation single-swap local-search algorithm for (p,q)-Clustering.
Takeaways & Limitations
The local-search algorithm is simple, implementable, and much faster than the prior algorithm, while achieving O(log ℓ) for ℓ1-Clustering by setting q = log ℓ.
Takeaways & Limitations
The analysis assumes q ≥ p and restricts scalar-cost coefficients to a bounded range m ≤ ξ_ab ≤ M.
Abstract
from arXiv · showhide
We study the Socially Fair Clustering problem introduced by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021), along with its extension, the $(p,q)$-Socially Fair Clustering problem. This problem generalizes $k$-medians and $k$-means to settings where data points are partitioned into $\ell$ groups, and the goal is to find a fair clustering that is simultaneously good for all groups. We present several algorithms for this problem. For $\ell_p$-Socially Fair Clustering, we give the first constant-factor FPT-approximation parameterized by the number of groups $\ell$, resolving the open question raised by Ghadiri, Singh, and Vempala (2022). Our main ingredient is a new algorithm for closing additional centers in parameterized time inspired by local search. We then turn to the more general $(p,q)$-Socially Fair Clustering problem. The known algorithm for this problem, proposed by Chlamtáč, Makarychev, and Vakilian (2022) achieves a very good approximation but is complex, slow and difficult to implement. We analyze the performance of a simple local search algorithm and show that it provides an $O(q)$ approximation in the worst case. Finally, we design approximation algorithms for the facility location variant of the problem, where the number of facilities (centers) is not fixed in advance, and opening each facility incurs an opening cost. Unlike in previous work, we do not assume these opening costs are the same for all groups.
1 Introduction
Socially Fair Clustering seeks solutions that perform well simultaneously across protected groups, addressing shortcomings of aggregate clustering objectives. The paper resolves an FPT approximation question for ℓp-Clustering, analyzes simple local search for (p,q)-Clustering, and develops facility-location algorithms with heterogeneous group costs.
- Motivation: Socially Fair Clustering evaluates clustering quality for all groups simultaneously, including overlapping groups that need not cover the dataset.Groups can represent minority or otherwise protected populations, with point weights encoding group membership.
- Problem formulations: For (p,q)-Clustering, group-specific p-norm costs are aggregated using an ℓq norm, while ℓp-Clustering uses the maximum across groups.The two formulations are equivalent when q = ∞, and q is assumed at least p to avoid favoring unfair clusterings.
- Contributions: The paper introduces a parameterized center-closing algorithm that converts a c-approximate solution with k + t centers into a (3c + 2 + ε)-approximate solution with k centers.Theorem 1.2 states that the algorithm runs in time parameterized by ℓ, p, t, and 1/ε.
- Contributions: A single-swap local search algorithm gives an O(q)-approximation for (p,q)-Clustering in at most O(kq log n) iterations.Its running time is O_p,q(n^2ℓk^2 log n), and for ℓ1-Clustering it yields O(log ℓ) by setting q = log ℓ.
- Contributions: For Socially Fair Facility Location, the paper achieves 4 + ε with homogeneous group costs and O(q / log q) with heterogeneous costs.For p = 1 and q = ∞, the heterogeneous-cost guarantee becomes O(log ℓ / log log ℓ).
Organization
The paper proceeds from proof overviews to an FPT algorithm for ℓp-Clustering, local search for (p,q)-Clustering, and facility location algorithms, with an appendix on bicriteria local search.
- Organization: Section 3 overviews the proofs, while Sections 4–6 cover FPT clustering, single-swap local search, and socially fair facility location, respectively.Appendix A presents a (3 + ε)-bicriteria local-search algorithm for ℓ1-Clustering.
2 Preliminaries
The preliminaries model fair clustering in a metric space with weighted groups and potential centers. Group costs form a vector whose aggregation defines the two clustering objectives.
- Problem setup: The input is a metric space with data points, potential center locations, group-weight vectors, and a target number k of centers.The i-th coordinate of w(u) gives point u’s weight for group i.
- Cost definitions: For each group, the ℓp-cost is computed from weighted distances to the nearest selected center.The cost is raised to the power p before taking the group-level p-root.
- Objective definitions: The resulting ℓ-dimensional cost vector is aggregated by its ℓ∞ norm for ℓp-Clustering and by its ℓq norm for (p,q)-Clustering.Thus, the former emphasizes the largest group cost, while the latter uses the specified q-norm aggregation.
3 Proof Overview
The proof overview develops an FPT approximation for ℓp-Clustering by starting from a bicriteria solution and closing additional centers. It also outlines local search for (p,q)-Clustering and rounding methods for facility location.
- FPT approximation for ℓp-Clustering: The ℓp-Clustering algorithm starts from a polynomial-time bicriteria solution with k + ℓ centers.In the ℓ1 case, a local-search-based bicriteria algorithm can provide a better approximation.
- FPT approximation for ℓp-Clustering: Closing t additional centers and reassigning their clients while controlling every group’s cost is the central challenge.An existential procedure closes centers and redirects clients to nearby remaining centers.
- FPT approximation for ℓp-Clustering: Color coding identifies the centers to close without access to the optimal solution.A suitable red-blue coloring separates closed centers from their receiving centers with probability at least 2^-2t.
- FPT approximation for ℓp-Clustering: Z-profiles summarize group-wise reassignment costs, allowing replacement centers with matching profiles to preserve the reassignment vector.The method discretizes profiles, guesses their multiplicities, and uses blue centers as proxies for unknown receiving centers.
- Local search and facility location: For (p,q)-Clustering, local search repeatedly performs improving one-for-one swaps and analyzes their distribution using derivative bounds, convexity, and the mean-value theorem.The facility location variants instead use rounding algorithms, including randomized rounding for heterogeneous opening costs.
4 FPT algorithm for ℓp-socially fair clustering
The FPT algorithm converts a bicriteria solution with k + t centers into a k-center solution by selecting t centers whose closure has controlled group-wise reassignment cost. Color coding and discretized profiles make this selection possible in fixed-parameter time.
- Algorithmic framework: The algorithm first obtains a c-approximate solution with k + t centers, then seeks to close t centers and retain k centers.For the main application, t is set to ℓ.
- Redirection and cost profiles: The reassignment operation moves clients of closed centers to designated receiving centers and records the increase separately for each group.The resulting vector is cost(α, C1, C2), whose coordinates are group-wise cost increases.
- Redirection and cost profiles: A suitable pair of sets C1 and C2 exists with |C2| ≤ |C1| = t, where C2 contains nearest open-center receivers for closed centers.This existential redirection keeps the reassignment cost controlled relative to the bicriteria solution.
- Color coding: Color coding finds a candidate pair by making all centers in C1 red and all centers in C2 blue, an event occurring with probability at least 2^-2t.Enumerating O(2^2t log n) colorings yields a good coloring with high probability.
- Profile matching and guarantee: The resulting k-center solution is obtained in n^O(1) time after closing ℓ centers from the bicriteria solution.The construction is combined with the initial polynomial-time approximation and the center-closing lemma.
5.1 Local search with scalar costs
This section develops the swap-distribution guarantees needed to analyze local search beyond linear k-median objectives. The framework controls scalar cost changes using carefully distributed swaps and bounded linearization multipliers.
- Setup: The analysis revisits local search for (k,p)-clustering before applying it to (p,q)-Clustering.It follows earlier k-medians and k-means analyses but requires finer control over swap distributions.
- Swap model: A local-search step replaces one current center with one target center and evaluates the expected scalar cost after the swap.The current and target center sets each contain k centers.
- Swap guarantees: The bounded coefficients arise by expressing nonlinear swap changes linearly through the mean-value theorem and convexity.The resulting guarantees bound changes in scalar costs, which are then used to control the objective.
5.2 Single swap analysis w.r.t. the (p, q)-objective
The local-search analysis handles the nonlinear (p,q)-objective by linearizing the inner transformation over the range of possible swap costs. A piecewise-linear approximation then supports a key expected-cost inequality and the existence of an improving swap.
- Objective and swap comparison: The (p,q)-Clustering local-search algorithm minimizes an objective built from group-level costs and analyzes swaps against an optimal solution.The analysis fixes an optimal center set and studies the cost after replacing one current center.
- Piecewise-linear approximation: For each coordinate, the analysis sets r = q/p and φ(t) = t^r, then bounds the range of post-swap values.The maximum value over supported swaps is denoted ˆz_i.
- Piecewise-linear approximation: φ is approximated on [0, ˆz_i] by two linear segments with slopes m and M.The slopes are selected using derivative bounds and the mean-value theorem.
- Improving swap: Summing the key inequality over all coordinates yields β = O(q), which implies the existence of an improving swap when the current solution is sufficiently worse than optimal.The inequality is obtained using the swap distribution from the preceding analysis.
5.3 Putting everything together
The local search analysis bounds the potential after termination and shows that the algorithm reaches an O(q)-approximate solution in a bounded number of iterations.
- The algorithm repeatedly selects the swap a → b that most decreases the potential Φ and stops when no sufficiently improving swap remains.
- Φ ≤ 2βqΦ∗ when the algorithm terminates, establishing the core potential bound.
- The algorithm returns a solution of cost at most O(q) in at most O(qk log n) iterations.
- Each swap can be evaluated using closest and second-closest centers, with per-swap work of O_p,q(nℓ).
5.4 Proof of Lemma 5.1
The proof constructs a swap distribution from the mapping between optimal and current centers, then bounds expected reassignment costs using profile and distance arguments.
- The map γ sends each optimal center to its closest current center and partitions centers into A0, A1, A⋆, B1, and B⋆ according to preimages.
- With r = |A1|, the partition guarantees |A0| ≥ (k − r)/2, enabling a probability distribution over swaps.
- For a reassigned point, the triangle inequality bounds its distance through the mapped optimal center and the swapped current center.
- The distribution selects swaps by choosing either an optimal center or centers uniformly from A0 and B⋆, yielding bounded marginal probabilities.
- The expected weighted cost change satisfies kE[ξab · (costab(w) − cost(w))] ≤ (1 + 2θ)M cost∗(w) − (m − 2δM) cost(w).
5.5 Proof of Inequality 7
The proof derives the desired approximation bound by selecting parameters that control the profile and cost inequalities.
- The analysis sets β = (2 · 4^(p+2) · r · (2T)^r)^(1/q) = O(q).
- The parameter choices bound α and establish that the relevant powered quantity is at most T.
6 Socially fair facility location
The paper studies socially fair facility location with homogeneous and heterogeneous opening costs, using convex relaxations and rounding algorithms to obtain approximation guarantees and hardness results.
- The facility-location model has ℓ groups, weighted clients, and either scalar group-homogeneous or vector group-heterogeneous opening costs.
- The group-uniform cost variant admits an (8 + ε)-approximation, while heterogeneous costs also have logarithmic hardness and LP integrality gaps.
- Group homogeneous facility costs: 4 + ε approximation is achieved for group-homogeneous facility costs by combining opening-cost and connection-cost bounds with α = 4/3.
- Group homogeneous facility costs: The homogeneous-cost algorithm rounds a convex relaxation by opening the cheapest facility in each selected ball and assigning nearby points to it.
- Group heterogeneous facility costs: The heterogeneous-cost algorithm instead randomly opens one facility per ball with probability proportional to its fractional target value.