Socially Fair Clustering: Parameterized Approximation and Local Search
Abstract
We study the Socially Fair Clustering problem introduced by Abbasi, Bhaskara, and Venkatasubramanian [2] and by Ghadiri, Samadi, and Vempala [14], along with its extension, the -Socially Fair Clustering problem. This problem generalizes -median and -means to settings where data points are partitioned into groups, and the goal is to find a fair clustering that is simultaneously good for all groups. We present several algorithms for this problem.
-
1.
For -Socially Fair Clustering, we give the first constant-factor FPT-approximation parameterized by the number of groups , resolving the open question raised by Ghadiri, Singh, and Vempala [15]. Our main ingredient is a new algorithm for closing additional centers in parameterized time inspired by local search.
-
2.
We then turn to the more general -Socially Fair Clustering problem. The known algorithm for this problem, proposed by ChlamtΓ‘Δ, Makarychev, and Vakilian [13], 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 -approximation in the worst case.
-
3.
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.
Keywords and phrases:
Socially fair clustering, Approximation algorithms, Fixed-parameter tractability, Local search, Facility location, k-median and k-meansCategory:
APPROXFunding:
Yury Makarychev: NSF award ECCS-2216899Copyright and License:
2012 ACM Subject Classification:
Theory of computation Facility location and clustering ; Theory of computation Fixed parameter tractabilityEditors:
Mohit Singh and Tom GurSeries and Publisher:
Leibniz International Proceedings in Informatics, Schloss Dagstuhl β Leibniz-Zentrum fΓΌr Informatik
1 Introduction
1.1 Overview
Today, computers are widely used to analyze and classify data, generate recommendations, and make decisions that affect many aspects of peopleβs lives. Traditionally, algorithms have focused on optimizing the overall quality of a solution. As a result, their decisions may be unfair to specific individuals or groups. Given the significance of these decisions, addressing fairness in algorithmic decision-making has become essential.
The -median and -means objectives are widely used in clustering and typically yield solutions that perform well for most data points. However, some points may be much farther from their assigned centers than others, and therefore incur disproportionately high costs. This is especially problematic when data points represent people, and those bearing the highest costs disproportionately belong to minority groups. Consider, for example, a facility location problem modeled using -median: we wish to open facilities (e.g., hospitals or grocery stores) in a city to serve all residents effectively. The goal is to minimize the sum of distances from each person (data point) to their nearest facility (center): . If a minority group resides in an isolated neighborhood, it is possible that none of the facilities will be placed nearby, leaving that group underserved.
To address this issue, [2] and [14] independently introduced the Socially Fair Clustering problem. This problem was also previously studied by [6] in the context of clustering under uncertainty. In the fair clustering setting, the data points belong to groups , representing minority or otherwise protected populations (the groups may overlap and do not have to cover ). The goal is to find a clustering that performs well for all groups simultaneously. It is convenient to assign weights to data points: for group , let denote the weight of point , where if and otherwise; one natural choice is for .
The -Socially Fair Clustering problem, referred to as -Clustering for brevity, asks for a set of centers from a set of potential centers that minimizes
| (1) |
ensuring that the solution performs well across all groups. In other words, we compute the -norm of distances for each group , and the objective aggregates these by taking a maximum (many papers define the objective as the -th power of ours; the two formulations are essentially equivalent: an -approximation for our objective corresponds to an -approximation for the alternative, and vice versa).
A more general variant of the problem, known as -Socially Fair Clustering with , employs a different aggregation function.111We assume that , since otherwise the objective would favor unfair clusterings. For example, let and . Suppose there are two candidate solutions: in the first, each group has -norm distance , while in the second, the -norms of the distances for the two groups are and (where the -norm distance of group is given by ). The corresponding aggregated objectives are and . Thus, we would prefer the second solution, even though it is clearly less fair. In this formulation, we construct a vector whose -th coordinate represents the -norm of the distances for group , and then take the norm of this vector:
| (2) |
We refer to this problem simply as -Clustering. When , the objective in (2) reduces to that in (1); thus, -Clustering and -Clustering are equivalent. Moreover, the -objective approximates the -objective within a constant factor. This follows from the more general fact that the and norms of a -dimensional vector are within a factor of of each other, which can be shown by a simple computation. Hence in all our results for -Clustering, we obtain results for -Clustering by setting .
1.2 Known results
The problem has been extensively studied since its introduction. We begin by summarizing previously published approximation algorithms. [6] gave an -approximation for -Clustering. [2] and [14] provided -approximation algorithms for -Clustering with . Additionally, [2] presented a bicriteria approximation algorithm that achieves a constant-factor approximation by opening centers.
The approximation factor was later improved by [22], who obtained an -approximation. This approximation factor is optimal under the assumption that , as was shown by [10]. Finally, [13] studied the -Clustering problem and gave an -approximation for it. This approximation factor matches that for -clustering when .
Another line of research has focused on designing fixed-parameter tractable (FPT) algorithms for -Clustering. In a significant result, [16] settled the approximability of -Fair Clustering for FPT algorithms parameterized by by designing a -approximation algorithm and proving a matching lower bound of . They also established lower bounds of and for the approximability of and -Clustering when parameterized by both and .
[15] observed that in practice, is typically a small constant, while may be very large. They presented a polynomial-time algorithm achieving a bicriteria approximation by opening at most centers. Building on the bicriteria result mentioned above, they also designed algorithms with running times and , achieving approximation factors of and , respectively. The latter is an FPT algorithm parameterized by both and . They then raised the question of whether there exists a FPT algorithm achieving a constant-factor approximation parameterized solely by . This question remained open until our current work.
We also note that the problem admits a -approximation when parameterized by for certain special classes of metric spaces, as shown by [1]. In many real-world applications, the number of centers β typically referred to as facilities in this context β is not fixed in advance. Instead, opening each facility incurs a cost. As is standard, we refer to this setting as the Facility Location problem. [2] presented a 4-approximation algorithm for the Facility Location variant of -Clustering, assuming homogeneous costs across groups (i.e., the cost of opening a facility is shared equally among all groups).
1.3 Other related work
The theme of fair clustering has received a lot of attention in recent years. Some other notions of fairness that have been adopted include balancedness [11], no over-representation [4], fair hierarchical clustering [3], individual fairness [20], pairwise fairness [9, 8]. Many of these incorporate constraints on clusters rather than enforcing fairness through a new objective, as is the case for Socially Fair Clustering.
1.4 Our results
1.4.1 FPT Algorithm parameterized by
In this paper, we address several important open problems in the field. First, we resolve the open question posed by [15] by presenting a constant-factor approximation FPT algorithm for -Clustering, parameterized by the number of groups .
Theorem 1.
For every , there exists a -approximation algorithm for -Clustering that runs in time .
We prove this result by designing a new algorithm that reduces the number of centers in fixed-parameter time.
Theorem 2.
There exists an algorithm that, given an instance of -Clustering, a -approximate solution with centers, and a parameter , returns a -approximate solution with centers. The algorithm runs in time .
Combining Theorem 2 with the following result of [15], we immediately obtain Theorem 1, thereby answering their open question.
Theorem 3 ([15]).
There is a bicriteria polynomial-time algorithm for -Clustering that finds a -approximate solution with centers.
1.4.2 Local Search Algorithm for -Clustering
The second theme of our paper is the design of a more efficient and implementable algorithm for -Clustering. The algorithm in [13] solves an exponential-size convex relaxation using the round-or-cut framework, which is impractical and difficult to implement. In contrast, local search algorithms are well known for their efficiency and ease of implementation. Previously, [7] showed how to obtain a -approximation for -median using a single-swap local search algorithm, and a -approximation using a multiple-swap variant. This result was generalized by [17], who gave an -approximation for the single-group case of -Clustering and showed that this analysis is tight β there are instances where the algorithm returns only an -approximate solution.
We analyze the performance of the single-swap local search algorithm on instances of -Clustering with an arbitrary number of groups , and show that it yields an -approximation. The aforementioned lower bound in [17] implies that our analysis is tight. While our approximation guarantee is worse than those of [22] and [13], it comes close in a particularly important case: -Clustering. For that problem, we obtain an -approximation by setting , which matches the best known approximation factor of up to a factor. Our algorithm is simpler, more implementable, and much faster than the algorithm of [13].222The running time in [13] is polynomial, but it is not stated explicitly.
Theorem 4.
There is a single-swap local search algorithm for the -Clustering problem that gives an -approximation, performs at most iterations and runs in time .
1.4.3 -Socially Fair Facility Location
Finally, we study the -Socially Fair Facility Location problem, an important and practically motivated variant of -Clustering. Building on the result of [2] for , we present a -approximation algorithm for -Socially Fair Facility Location with homogeneous costs. We then consider a more general setting with heterogeneous costs, where different groups incur different facility opening costs. In this case, we obtain an -approximation; in particular, for , this yields an -approximation333We recall that the objective approximates the objective up to a constant factor, which almost matches the approximation hardness of for this problem; see the full version for details.
Theorem 5.
For Socially Fair Facility Location with group-homogeneous facility cost, there exists a polynomial-time algorithm that achieves a -approximation for any .
Theorem 6.
For Socially Fair Facility Location with group-heterogeneous facility cost, there exists a polynomial-time algorithm that achieves an -approximation.
Organization
Section 3 gives an overview of the proofs of our results. In Section 4, we present our fixed-parameter tractable (FPT) algorithm for -Clustering. In Section 5, we analyze a simple single-swap local search algorithm for -Clustering. In Section 6, we describe our algorithm for -Socially Fair Facility Location. In the full version of the paper, we give a -bicriteria local-search algorithm that opens centers for -Clustering.
2 Preliminaries
This paper focuses on the and -Fair Clustering Problems, referred to below simply as - and -Clustering. In these problems, we are given a metric space , where the points represent data points or clients, and a set of potential center or facility locations . Let be the number of data points or clients. For each point , we are also given a vector of weights , where the -th coordinate denotes the weight for group . We denote the number of groups by . The goal is to select a subset of centers that minimizes objective (1) for -Clustering and (2) for -Clustering.
To analyze these objectives, we define the -cost of the clustering (raised to the power ) with respect to a weight function and centers as
where . We then define the cost vector induced by weights and centers as the -dimensional vector whose -th coordinate is . Then the -objective in (1) is the -norm of the cost vector, while the -objective in (2) is its -norm.
We will need the following claim.
Claim 7 (see e.g. Lemma A.1 in [21]).
For all non-negative real numbers and , and for every and , we have
3 Proof Overview
In this section, we offer a technical overview of the proofs of our main results. We focus primarily on the fixed-parameter tractable (FPT) approximation algorithm for -Clustering parameterized by the number of groups (Section 4), and then briefly describe the ideas underlying the remaining results.
3.1 FPT approximation for -Clustering (Section 4)
Our goal is to design a constant-factor approximation algorithm for -Clustering that runs in time , parameterized only by the number of groups . As a starting point, we run the algorithm of [15] (see Theorem 3) to get a -approximate solution with at most centers in polynomial time. In the special case of -Clustering, we can alternatively use the local-search-based bicriteria approximation algorithm (see the full version of the paper), which yields a better approximation. Let denote the resulting set of centers, where , and let be the corresponding approximation factor.
Given such a bicriteria solution, the main challenge is to close centers and reassign the clients assigned to them to other centers, while controlling the cost increase for all groups. We proceed in two steps. First, we show that existentially it is possible to close centers and reassign every client assigned to a center in to the center closest to in so that the cost of the resulting solution is within a constant factor of the cost of (see Lemma 9 for the exact guarantee). The key idea is that the new connection cost for a client can be bounded in terms of both the cost of connecting to its originally assigned center in and the cost of connecting to the center serving in the optimal solution . This observation is important because it allows us to reassign the clients assigned to the closed centers to at most centers (that are not closed), and this property is crucial for our algorithm.
However, we cannot use the procedure from Lemma 9 directly, as it requires knowledge of . Thus, to obtain an FPT algorithm, we need to identify the set without access to the optimal solution. This is achieved using the technique of color coding introduced by [5]. Let be the set formed by selecting, for each , a closest center to in . Note that (each center contributes at most one selected center; and different centers in may potentially have the same closest center in ). We color all centers in randomly using two colors, red and blue. Each center is colored red or blue independently with probability . Note that with probability at least , all centers in are colored red and all centers in are colored blue. By running the algorithm times, we obtain a coloring with this property with high probability. We denote the sets of red and blue centers by and , respectively.
Now, we introduce the notion of a -profile of a center . Loosely speaking, the -profile is a vector in that captures, for each of the groups, the reassignment cost incurred by closing center and reassigning all clients assigned to to the center closest to in . Crucially, the -profiles of all centers in fully determine the reassignment cost: the reassignment cost vector is simply the sum of the -profiles of all centers in . Importantly, if we were to find another set of centers in with the same profiles, the reassignment cost would be the same. However, there are two challenges in finding such a set. First, as defined, the number of possible profiles is unbounded. Second, since we do not know the set , we cannot compute the -profiles of centers in .
To resolve the first issue, we discretize the set of all possible profiles so that their number is bounded by a function of , , , and . We then βguessβ the number of centers in with each possible profile. Next, we observe that the -profiles and -profiles of centers in are equal, and thus we can use as a proxy for . We select centers in according to our guess of the profile counts and obtain a set of centers to close. Given the discussion above, it is not hard to see that by closing the centers in and reassigning clients to their closest centers in , we obtain a constant-factor approximation.
3.2 Local search for -Clustering (Section 5)
Building on the local search algorithms from [7] and [17] for -median, -means, and -clustering, we design and analyze a local search algorithm for the more general -Clustering problem. The general approach is similar to that of [7] and [17], but the analysis is more complex, as it requires fine-grained control over the distribution of swaps (see below).
The algorithm starts with an arbitrary set of centers and repeatedly finds and performs a swap that replaces one of the centers with a center outside of . The swaps are chosen to minimize the -Clustering objective, and the algorithm terminates when no swap decreases the current potential by more than . To prove that the algorithm achieves an -approximation, we show that if the cost of the current solution exceeds the optimal cost by times, then there must exist an improving swap. To this end, we present a distribution over special swaps that replace centers in with centers in an unknown optimal solution (The algorithm may choose a swap from the distribution or any other swap improving the objective; we use the distribution only for the analysis). While this approach resembles that of [7] and [17], we require significantly more control over the distribution of swaps to handle the more complex objective. In particular, we use careful linear approximations for the change in the non-linear objective that allow us to show that there is indeed such a distribution over improving swaps.
To obtain these linear approximations, roughly speaking, we can obtain upper and lower bounds on the derivative of the cost function in the desired range. One can then use the mean-value theorem to find a linear approximation of the change in the objective using these bounds. The actual proof is slightly different, and uses convexity arguments along with the mean value theorem. Carefully combining this with the standard linear-objective analysis for -Median, we show that the algorithm is an approximation.
3.3 Socially Fair Facility Location (Section 6)
Finally, we study -Socially Fair Facility Location. We consider two variants of the problem: facility location with homogeneous opening costs and facility location with heterogeneous opening costs. For the homogeneous case, we use a rounding algorithm inspired by the standard facility location algorithm of [23]. For the heterogeneous case, we replace the greedy step that selects and opens the cheapest facility within a certain ball with a randomized rounding step that opens a facility in with probability proportional to the target probability given by the convex relaxation. We then use Rosenthalβs inequality to bound the expected -norm of the solution. We also give a hardness result showing that our algorithm is near-optimal for -Socially Fair Facility Location (the case when , ).
4 FPT algorithm for -socially fair clustering
As discussed in the introduction, we provide an FPT algorithm for -Clustering, parameterized by the number of groups . The algorithm first finds an approximate solution with centers using Theorem 3. This solution provides only a bicriteria approximation. To obtain a true approximation, the algorithm closes centers β using Theorem 2.
We now proceed with the proof of Theorem 2. Given the instance of -Clustering on point set and metric , a set of centers and an assignment , we define the cost with respect to the weight function and assignment as follows:
Note that the -objective function for the assignment is then . Throughout this section, we fix an optimal set of centers and a corresponding optimal assignment . Let us define to be the optimal assignment -objective, so that .
First, we show that given any set of centers which is a -approximate solution, indeed there exists a subset of centers that can be closed such that the resulting subset of -centers is a -approximate solution. However, besides this, we show a stronger property that our algorithm requires: every client assigned to some center of (in an optimal assignment of clients to ) that is closed in this process can now be reassigned to one of at most open centers in . The next key lemma proves this result. Before we state the lemma, the following definition will be useful.
Definition 8.
Given a set of open centers , an assignment of points to centers in , and two disjoint subsets , we define a new assignment obtained from by reassigning clients as follows. For each client , if , we find the closest center in to and let . If , we set (do not change the assignment).
We then define to be the vector with for each .
Simply put, measures the increase in cost for group (coordinate) by re-assigning each point assigned to a center to the center in closest to . We use the shorthand to denote . If is an optimal assignment, then is coordinatewise non-negative, since any reassignment can only increase the cost. We also have:
| (3) |
We formalize this nearest-neighbor redirection operation in the following lemma, showing that one can close a set of centers and reassign all affected clients to a set of at most receiving centers while keeping the reassignment cost controlled. The redirection operator in the definition captures exactly what happens when we close centers : for each closed center , we send all of its clients to the closest open center . Let be the set of such receiving centers.
Lemma 9.
Given a -approximate solution with centers and a corresponding optimal assignment of clients to centers in , there exist disjoint sets with such that
-
-
is the closest point from to for some .
Proof.
Let be an optimal set of centers, and let be an optimal assignment of clients to the centers in . For each , mark , the closest center to in . Then there are at most marked centers in and at least unmarked ones. Choose any subset of unmarked centers in to be the set . For each center of , we take the closest center in to obtain the set . Note that this means .
We now show that this choice of satisfies the statement of the lemma. Let and let be the closest center to in (which must be in ). Then, for every point with , we reassign to .
We wish to bound the reassignment cost of to . Let be βs assigned center in . By the triangle inequality,
It follows from Claim 7 that for every , we get the inequality
We can now use this to bound the change in cost. By definition, it follows that the contribution of client to is . Now repeating the analysis for each point , and recalling that , we obtain
where we use the fact that and , since is a -approximate solution.
Now we set . It then follows that
Next, we describe how to find such sets in FPT time. We will use the color coding technique of [5]. We remark that while our algorithm is stated as a randomized algorithm for simplicity, it can be easily derandomized using standard techniques (see, for example, [12, Lemma 1]).
Lemma 10.
Given a -approximate solution with centers and a corresponding optimal assignment of clients to centers in , one can find disjoint sets with satisfying in time .
Proof.
Let be the (unknown) subsets of guaranteed by Lemma 9. We use color coding. Randomly and independently color each center in red or blue, each with probability . Call a coloring good if every center of is colored red and every center of is colored blue. Then a random coloring is good with probability at least . By independently sampling random colorings, we can ensure that we enumerate a good coloring with high probability. Henceforth, assume that we are given a good coloring (we will try all the colorings). Let be the red-colored centers, and be the blue-colored centers in this good coloring.
For a set , we say that the -profile of is if the -th coordinate of is in the interval for each . Here are positive integers. Let be the set of profiles with all . Then . Note that the -profile of every lies in . This is the case because, for every coordinate , (1) , since is an optimal assignment, and (2) by (3) and Lemma 9.
For each profile , guess the number of centers in with -profile . Let denote this number for each . Then . The number of guesses we need to make is at most .
Consider and let be the closest point to in . Note that (per item 2 in Lemma 9) and is also the closest point to in , since . Therefore, the - and -profiles of are the same. In particular, there are centers with -profile in . Since all centers in are red (recall that we assumed that the coloring is good), there are at least red centers with -profile .
Now for each , we choose exactly red centers whose -profile is to form the set 444While we do not know , we can guess up to a factor of , but we omit this detail in the proof for the sake of simplicity. Once we choose , we let be the set of all centers such that is the closest center in to some . This concludes the construction of the sets and .
Lemma 11.
.
Proof.
There is a one-to-one map such that the -profile of and the -profile of are the same for every .
It follows that for every and every coordinate ,
The term is exactly the length of an interval in the definition of profiles. Summing this upper bound on over all and using (3), we get
Proof of Theorem 2.
Let be an optimal assignment for the center set . Invoke Lemma 10 to obtain the sets . After obtaining the sets , we close the centers . Since , it follows that we obtain a solution with at most centers.
We have , and by Lemma 10, the additional cost incurred is at most . Thus the -objective of the resulting solution with centers is at most where in the final step we use the inequality , which holds for every .
5 Local search algorithm for -clustering
5.1 Local search with scalar costs
Following [7] and [17], we first revisit the local search algorithm for -clustering. We will later apply the results of this section to analyze the performance of the local search algorithm for -Clustering.
Let be a metric space, and let be non-negative vertex weights. We consider one step of the local search algorithm. Let be the current set of centers, and be a target set. Later, will be an optimal solution for the -objective, but for now, we make no assumptions about it.
We define the cost of as
and the cost of as
Consider a swap operation that replaces with . We denote the resulting set of centers by
and its cost by .
Consider a probability distribution on the set of swaps (equivalently, on ). The expected cost after a random swap drawn from is .
We derive the following guarantees for local search. Conceptually, the proof closely follows the analyses in [7] and [17]. However, the bounds we require are more intricate, as we need finer control over the distribution of swaps. We prove this lemma in Section 5.4.
Lemma 12.
Let be a metric space, and let and be two sets of centers. There exists a probability distribution over swaps such that the following holds. For every , weights , parameters , and coefficients , we have:
-
1.
For , the following inequality holds.
(4) -
2.
We also have:
(5) -
3.
Finally, for every swap in the support of and every , we have
(6) where .
At a high level, the necessity for such guarantees is as follows. In -median, the objective is linear, and the effects of the change in cost due to a single swap can be directly accounted for. However, in -Clustering, the objective involves two layers of non-linearity (the inner and outer norms). To deal with this non-linearity, we can write the change in the objective for each swap as a linear change with multipliers using the mean value theorem and convexity. Here the multipliers are bounded in the range for some appropriate choice of and . The above lemma then assumes this boundedness of and derives guarantees on the change in , which in turn bounds the change in the objective.
5.2 Single swap analysis w.r.t. the -objective
Now we consider the local search algorithm for -Clustering β the goal is to minimize the following objective function:
From now on, let be an optimal solution for the -Clustering problem. We assume that swap is sampled from distribution constructed in Lemma 12. Define and , and
Note that is the cost of the optimal solution, is the cost of the current solution, and is the cost of the solution after a swap . Also, let
Fix a coordinate . Now we get an upper bound for by approximating with a piecewise linear function. Let be the maximum of over all swaps in the support of (we will obtain an upper bound on later using Lemma 12, item 3). Let and . Note that when , by the Mean Value Theorem and monotonicity of . Since is convex, we have (see Figure 1)
Define coefficients as follows
Then , and we have .
We are now in a position to use Lemma 12, from which we derive the following key inequality, whose proof is deferred to Section 5.5.
| (7) |
with . Adding up the inequality over all coordinates , we get
In particular, this means that there is always a swap , for which
5.3 Putting everything together
Consider the local search algorithm that at each iteration finds a swap with and that produces the greatest decrease in the potential function , where is the current set of open centers and is the candidate facility set. The algorithm terminates when no swap decreases the current potential by more than .
5.3.1 Bounding the number of iterations
Suppose that . Then, for the improving swap identified above, we have
and
Thus when the algorithm stops, we must have . Until the algorithm stops, in every iteration, the above inequality holds. It follows that after at most iterations, the algorithm will find a clustering of cost at most .
As is standard, by truncating distances and rounding weights, we may assume that all distances and weights are integers bounded polynomially in . Therefore, the cost of any clustering is polynomial in ; hence, is bounded by . We conclude that the algorithm returns a solution of cost at most in at most iterations.
5.3.2 Running time per iteration
In each iteration, we maintain the current set of centers . For each point , we maintain its closest and second-closest centers and in . At the beginning of every iteration, these quantities can be computed in time . We can compute the change in cost due to a swap for each point using and the distances . Then we add these costs for each group in time and re-compute the potential. Thus, for every swap , we spend time and there are swaps, giving a per-iteration running time of . Since there are iterations, the running time is at most . This concludes the proof of Theorem 4.
5.4 Proof of Lemma 12
In this Section, we prove Lemma 12.
Proof.
Defining the distribution of swaps.
For each center , let denote the nearest center in (see Figure 2). We partition the centers in based on the number of preimages under :
-
: centers with exactly one preimage,
-
: centers with no preimages,
-
: centers with two or more preimages.
Define and . We observe:
-
is a one-to-one map between and ,
-
maps onto , with every having at least two preimages.
Denote . From the observations above, we get and . Thus, . Now we are ready to define a probability distribution over swaps.
-
1.
With probability , select uniformly at random and set ,
-
2.
With probability , select uniformly from and uniformly from .
This yields a random swap . Note that is uniformly distributed in and therefore the probability that is for every fixed . In general, is not uniformly distributed; however, for every fixed , the probability that is at most :
| (8) |
We will need below that for all ,
| (9) |
Indeed, in item 1, ; in item 2, . In either case, .
Upper bounding connection cost
Let denote the distance from to the closest center in the current solution , the updated distance after the swap, and the distance to the closest center in . Let be the Voronoi cell of in , and the Voronoi cell of in . For ,
For , assume for some . By (9), ; thus, and
Here, we used that , since is the nearest center in to .
Finally, if , then . We have,
| (10) | ||||
| (11) |
We now derive an upper bound for . Since , we can replace with in positive terms and with in negative terms. We have:
Now we assume that the swap is sampled from the distribution defined above. We get
From 8, we get and and thus
| (12) |
We will use (12) to derive (4), (5), and (6). We will use different values of parameters , , and in these derivations. We will need the following lemma.
Lemma 13.
For every and every value of , there exists such that and .
Proof.
If , we let , resulting in and , and we are done. If , we choose so that . Applying the Mean Value Theorem, we get
where we used that and . Therefore,
5.5 Proof of Inequality 7
Applying Lemma 12, we get for ,
| (13) | ||||
| (14) |
From Lemma 12, item 3, with and
we get
| (15) |
Fix a threshold . Consider two cases.
Current cost is small:
Current cost is large:
6 Socially fair facility location
In this section, we consider two variants of the Socially Fair Facility Location problem and provide approximation algorithms for them.
We are given a set of points and a metric on it, forming a metric space , as well as a set of possible facility locations . There are groups on represented by a weight function where denotes the weight of client in group . Each facility is associated with a facility opening cost . We consider the following two settings with different types of facility opening costs: (1) group-homogeneous facility cost; (2) group-heterogeneous facility cost.
Group-homogeneous facility costs
Each facility has a scalar opening cost , paid equally across groups. The objective is to choose minimizing
where .
[2] studied this objective with and and gave a -approximation algorithm for it.
Group-heterogeneous facility costs
Each facility has a vector opening cost , where group pays to open .555We interpret as a group-specific fixed charge for opening facility (e.g., taxes/subsidies or administrative overhead). Thus, group pays whenever is opened, regardless of whether any group- client is assigned to ; this keeps opening costs dependent only on the opened set , as in standard fixed-charge facility location.
In this case, the objective is666If the heterogeneous opening costs are group-uniform, i.e., for all and , then the objective becomes . We refer to this as the group-uniform cost variant. This objective is generally different from the group-homogeneous facility costs above. The two coincide when , but they differ for finite . By using our heterogeneous convex relaxation with and applying the rounding scheme used for the homogeneous costs, we obtain an -approximation for this group-uniform cost variant.
We get the following results for homogeneous and heterogeneous facility costs.
We now provide the approximation algorithm for the group-heterogeneous setting.
Proof of Theorem 6.
We use a relaxation of the problem and then use a randomized rounding procedure to get an integer solution. We consider the following relaxation
| min | ||||||
| s.t. | ||||||
| (16) | ||||||
| (17) | ||||||
| (18) | ||||||
| (19) | ||||||
We can binary search on . For any fixed value of , the relaxation above is convex.
We then apply the following randomized rounding algorithm inspired by [19, 24]. Let denote the fractional solution to the convex program above. The key difference is that, instead of opening the cheapest facility in , we open exactly one facility in selected randomly with probability proportional to . For each point , let denote the connection cost of point given by the fractional solution. Then, we sort all points in by their connection costs in increasing order. We iteratively perform the following steps until all points are assigned to open facilities. We first pick the unassigned point with the smallest connection cost as an anchor point. Let be all facilities in a ball with radius centered at . It can be shown that the balls corresponding to distinct anchor points are disjoint. Then, we sample exactly one facility in with probability proportional to . Assign all unassigned points with distance to this new facility . Let be the set of centers sampled by the rounding algorithm.
We now analyze the cost of this integer solution given by the rounding algorithm. Let be the indicator variable to denote whether facility is selected in . We first analyze the facility opening cost of this solution. By a simple averaging argument, for each iteration with anchor node , we have . Since we open exactly one facility in with probability proportional to , we have, for each facility ,
Consider any fixed group . For each iteration with anchor point , we define a random variable which represents the contribution to the facility cost of group from that iteration. Since the choices made in distinct, disjoint anchor balls are independent, the collection forms a set of independent non-negative random variables. By the Rosenthal inequality (see [18]), we have
Note that in each iteration, exactly one facility in is opened, which means exactly one random variable and all other in . Thus, we have
Hence, we have . We also have
Therefore, we have
By taking the sum over all groups and applying Markovβs inequality, with probability at least , we have
We then analyze the connection cost of this integer solution. If is assigned when is the anchor, then and . Hence, the connection cost for each group given by is at most
By combining with the facility opening cost, the facility location cost is at most
Therefore, by computing a -approximate solution to the convex relaxation, this randomized rounding provides the desired approximation with probability at least .
References
- [1] Fateme Abbasi, Sandip Banerjee, JarosΕaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, DΓ‘niel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized approximation schemes for clustering with general norm objectives. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 1377β1399, 2023. doi:10.1109/FOCS57990.2023.00085.
- [2] Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian. Fair clustering via equitable group representations. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 504β514, 2021. doi:10.1145/3442188.3445913.
- [3] Sara Ahmadian, Alessandro Epasto, Marina Knittel, Ravi Kumar, Mohammad Mahdian, Benjamin Moseley, Philip Pham, Sergei Vassilvitskii, and Yuyan Wang. Fair hierarchical clustering. Advances in Neural Information Processing Systems, 33:21050β21060, 2020.
- [4] Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over-representation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 267β275, 2019. doi:10.1145/3292500.3330987.
- [5] Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844β856, 1995. doi:10.1145/210332.210337.
- [6] Barbara Anthony, Vineet Goyal, Anupam Gupta, and Viswanath Nagarajan. A plant location guide for the unsure: Approximation algorithms for min-max location problems. Mathematics of Operations Research, 35(1):79β101, 2010. doi:10.1287/MOOR.1090.0428.
- [7] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for -median and facility location problems. SIAM Journal on Computing, 33(3):544β562, 2004. doi:10.1137/S0097539702416402.
- [8] Sayan Bandyapadhyay, Tianzhi Chen, Zachary Friggstad, and Mahya Jamshidian. A constant-factor approximation for pairwise fair k-center clustering. In International Conference on Integer Programming and Combinatorial Optimization, pages 43β57. Springer, 2025. doi:10.1007/978-3-031-93112-3_4.
- [9] Sayan Bandyapadhyay, Eden ChlamtΓ‘Δ, Zachary Friggstad, Mahya Jamshidian, Yury Makarychev, and Ali Vakilian. A polynomial-time approximation for pairwise fair -median clustering. In The 29th International Conference on Artificial Intelligence and Statistics, 2026.
- [10] Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann. New approximability results for the robust k-median problem. In Scandinavian Workshop on Algorithm Theory, pages 50β61. Springer, 2014. doi:10.1007/978-3-319-08404-6_5.
- [11] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. Advances in neural information processing systems, 30, 2017.
- [12] Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and MichaΕ Pilipczuk. Designing fpt algorithms for cut problems using randomized contractions. SIAM Journal on Computing, 45(4):1171β1229, 2016. doi:10.1137/15M1032077.
- [13] Eden ChlamtΓ‘Δ, Yury Makarychev, and Ali Vakilian. Approximating fair clustering with cascaded norm objectives. In Proceedings of the Symposium on Discrete Algorithms (SODA), pages 2664β2683, 2022. doi:10.1137/1.9781611977073.104.
- [14] Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala. Socially fair k-means clustering. In Proceedings of the ACM Conference on Fairness, Accountability, and Transparency, pages 438β448, 2021. doi:10.1145/3442188.3445906.
- [15] Mehrdad Ghadiri, Mohit Singh, and Santosh S Vempala. Constant-factor approximation algorithms for socially fair -clustering. arXiv preprint arXiv:2206.11210, 2022. doi:10.48550/arXiv.2206.11210.
- [16] Dishant Goyal and Ragesh Jaiswal. Tight fpt approximation for socially fair clustering. Information Processing Letters, 182:106383, 2023. doi:10.1016/J.IPL.2023.106383.
- [17] Anupam Gupta and Kanat Tangwongsan. Simpler analyses of local search algorithms for facility location. arXiv preprint arXiv:0809.2554, 2008. arXiv:0809.2554.
- [18] William B Johnson, Gideon Schechtman, and Joel Zinn. Best constants in moment inequalities for linear combinations of independent and exchangeable random variables. The Annals of Probability, pages 234β253, 1985.
- [19] Adam Kasperski, Adam Kurpisz, and PaweΕ ZieliΕski. Approximability of the robust representatives selection problem. Operations Research Letters, 43(1):16β19, 2015. doi:10.1016/J.ORL.2014.10.007.
- [20] Sepideh Mahabadi and Ali Vakilian. Individual fairness for k-clustering. In International conference on machine learning, pages 6586β6596. PMLR, 2020. URL: http://proceedings.mlr.press/v119/mahabadi20a.html.
- [21] Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Performance of johnsonβlindenstrauss transform for -means and -medians clustering. SIAM Journal on Computing, 52(2):269β297, 2022.
- [22] Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In Conference on Learning Theory, pages 3246β3264. PMLR, 2021. URL: http://proceedings.mlr.press/v134/makarychev21a.html.
- [23] David B Shmoys, Γva Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In Proceedings of the Symposium on Theory of Computing, pages 265β274, 1997.
- [24] Aravind Srinivasan. Approximation algorithms via randomized rounding: a survey. Series in Advanced Topics in Mathematics, Polish Scientific Publishers PWN, pages 9β71, 1999.
