Serving Clients Fairly: On Facility Location and $k$-Median with Fair Outliers

We first study facility location with fair outliers problem for arbitrary number of groups in Section 3 to give a $O(1/ϵ)$ factor approximation for the problem with $(1+2ϵ)$ factor violation in the outliers for any group. In particular, we present Theorem 3.

Inamdar and Varadarajan [27] gave an $O(\log \omega )$-approximation for the facility location problem with fair outliers for arbitrary $\omega$. More recently, Bajpai et al. [4] studied the case of a constant number of groups and obtained a 4-approximation. However, both these results rely on solving an exponentially large linear program using the ellipsoid method, and are therefore impractical to implement even for small values of $\omega >1$.

We will show that the standard LP formulation for the problem has unbounded integrality gap even when $\omega =1$ and hence we present a bi-criteria algorithm using LP rounding technique. Moreover, for arbitrary $\omega$, there is a known hardness of $\mathrm{\Omega }(\log \omega )$ due to [27] unless $P=NP$ ruling out any proper (as opposed to bi-criteria) polynomial-time approximation algorithm for an arbitrary number of groups.

In this paper, we also give a stronger hardness result. In particular, we show via a series of reductions that the problem Facility Location with Outliers is W[1]-hard parameterized by $\omega$.

A problem is W[1]-hard with respect to a parameter $k$ if no algorithm can solve it in time $f(k)\cdot \text{poly}(n)$, where $f(k)$ is an arbitrary function of $k$, and $n$ is the size of the input.

We next study the $k$-median with fair outliers problem in Section 4, where we present a bi-criteria approximation algorithm. To the best of our knowledge, the only prior practical result for this problem is the bi-criteria approximation by [1]. They gave a constant-factor approximation, however, their algorithm allows a violation of factor in $3k+2$ outliers per group, which can be prohibitive in practice, especially when $k$ is large. In contrast, our algorithm eliminates this dependence on $k$ in the violation bounds, making it more practical and scalable. The result is formally stated in Theorem 5.

The $k$-Median formulation presents unique algorithmic challenges and remains essential for practical applications. Historically, $k$-Median with outliers has proven far more complex to approximate than its Facility Location counterpart (FLO). While FLO admits straightforward 2-factor greedy or 3-factor primal-dual approaches, $k$-Median with outliers requires more sophisticated techniques, such as Lagrangian relaxation combined with iterative local search to achieve a constant-factor approximation [15], or iterative rounding on strengthened LPs to reach a 7.081 factor [23]. Furthermore, $k$-Median cannot always be emulated by FL because it enforces a hard cardinality budget $k$. In real-world scenarios with absolute funding or land-use limits – such as siting a fixed number of fire stations or hospitals – an FL formulation may produce a solution that opens more facilities than the budget allows, rendering it physically or financially infeasible. By explicitly bounding the facility count, $k$-Median ensures the solution remains within strict resource boundaries despite the added computational difficulty.

We also show that the hardness result for facility location extends to the $k$-median with fair outliers problem with slight modification in the reduction. In particular, we prove the following.

Finally, we implement our facility location and $k$-median algorithms and evaluate their performance on a real-world and synthetic datasets. For the facility location problem with fairness constraints, even for small values of $\omega$ (e.g., 2 groups), existing approximation algorithms [27, 4] – though polynomial-time – are impractical due to their reliance on solving exponentially large linear programs via the ellipsoid method. In contrast, our bi-criteria algorithm is significantly more efficient in practice. Empirically, it consistently outperforms its worst-case guarantees in both cost and fairness.

In summary, we observe that fairness our algorithms can ensure fairness with minimal increase in the cost of the solution with respect to non-fair algorithms (facility location with outliers).

For the $k$-median problem, we implement the bi-criteria algorithm and compare its performance – in both cost and fairness – against the non-fair variant, namely $k$-median with outliers [13]. Similar to the facility location case, we find that (i) our algorithm consistently outperforms its worst-case guarantees in practice, and (ii) it achieves significantly better fairness, while incurring virtually no increase in cost compared to the unfair baseline. We do not directly compare with Almanza et al. [1], as their experiments focus on the $k$-means objective, whereas our focus is on $k$-median. Nonetheless, our empirical findings support their conclusions in the context of the $k$-median objective as well.

The rest of the paper is organized as follows. In Section 2, we review the related work. Sections 3 and 4 give details of approximation algorithms for facility location with fair outliers and $k$-median with fair outliers respectively. In Section 5 we layout our experimental results for facility location. The experimental results for $k$-median can be found in Section 6. The proof of W[1] hardness is discussed in Appendix A. Proofs of statements marked by $†$ can be found in the appendix.

We now identify the set of clients to be treated as outliers in our solution. The idea is to declare a client as an outlier if it is predominantly an outlier in the LP solution ${\rho }^{\ast }$. For a given $ϵ>0$, we partition the client set $C$ into:

1. (i)

   $C_o=\{j\in C:z_j^{\ast }\ge 1-ϵ\}$

2. (ii)

   $C_r=C\setminus C_o$

We define a new solution $\widehat{\rho }=⟨\widehat{x},\widehat{y},\widehat{z}⟩$ as follows:

1. (i)

   For $j\in C_o$, set ${\widehat{z}}_j=1$ and ${\widehat{x}}_{ij}=0$ for all $i\in ℱ$.

2. (ii)

   For $j\in C_r$, set ${\widehat{z}}_j=z_j^{\ast }$ and ${\widehat{x}}_{ij}=x_{ij}^{\ast }$ for all $i\in ℱ$.

3. (iii)

   For all $i\in ℱ$, set ${\widehat{y}}_i=y_i^{\ast }$.

For any group $g\in [\omega ]$, we observe:

Moreover, $\text{cost}(\widehat{\rho })\le \text{cost}({\rho }^{\ast })$.

We now scale the assignment variables for $j\in C_r$ so that each such client is fully served, while maintaining feasibility. Let ${\rho }^{\prime }=⟨x^{\prime },y^{\prime },z^{\prime }⟩$ be the updated solution:

1. 1.

   For all $j\in C_r$ and all $i\in ℱ$, set:

   $$x_{ij}^{\prime }=\frac{{\widehat{x}}_{ij}}{{\sum }_{i\in ℱ}{\widehat{x}}_{ij}}.$$

2. 2.

   For each $i\in ℱ$, set:

   $$y_i^{\prime }=\min \{1,{\widehat{y}}_i\cdot \underset{j\in C_r:{\widehat{x}}_{ij}>0}{\max }\left\{\frac{x_{ij}^{\prime }}{{\widehat{x}}_{ij}}\right\}\}.$$

Note that for $j\in C_r$, ${\sum }_{i\in ℱ}{\widehat{x}}_{ij}\ge ϵ$, so:

It follows that ${\rho }^{\prime }$ is a fractional feasible solution to the standard Facility Location problem with client set $C_r$, and:

Let $⟨\overline{x},\overline{y}⟩$ be a solution to the Facility Location problem on $C_r$ with cost at most $\alpha \cdot {\mathrm{LP}}_{C_r}$, where ${\mathrm{LP}}_{C_r}$ is the cost of the optimal solution to the LP relaxation restricted to $C_r$. Then, the solution $⟨\overline{x},\overline{y},\widehat{z}⟩$ constitutes a $\frac{\alpha }{ϵ}$-approximate solution to the Facility Location with Fair Outliers problem, violating the group outlier bounds by at most a factor of $(1+2ϵ)$. Hence, we obtain the following theorem.

Note that once the set of outliers has been identified, any standard facility location algorithm [29, 3, 16] can be applied to determine which facilities to open for the remaining clients. In our experiments, after removing the outliers, we use a simple heuristic for facility location in which we directly round the fractional facility openings and assign remaining clients to nearest facility. The variable values are in fact close to 0/1. This is the primary reason we do not violate the outlier or cost constraints once we solve the LP.

We design our approximation for $k$-Median with Fair Outliers as follows:

1. 1.

   Guess the optimal cost ${\mathrm{OPT}}_C$ of the $k$-Median with Fair Outliers instance within a factor $(1+\epsilon )$.

2. 2.

   For each group $g\in [\omega ]$ and each client $j\in C_g$, set the penalty $p_j=\frac{{\mathrm{OPT}}_C}{\gamma \cdot {\mathrm{\ell }}_g},$ where $\gamma >0$ is a parameter to be chosen.

3. 3.

   Solve the corresponding $k$-Median with Penalties instance with penalties $\{p_j\}$ using the 4-approximation algorithm from Theorem 8.

4. 4.

   Let $F$ be the set of opened facilities, $C_o$ be the set of outliers paying penalties, and $\sigma$ be the assignment of remaining clients $C\setminus C_o$, then output $F$ as the set of opened facilities, $C_o$ as the set of outliers, and $\sigma$ as the assignment of remaining clients $C\setminus C_o$ for the $k$-Median with Fair Outliers instance.

We use a dataset inspired by Snyder and Daskin [40]. In their paper, they study the facility location from the lens of reliability after the failure of some constructed facilities. We use two of their datasets and pull key pieces of information for our application. The two datasets we use are a 49-node set on the capital cities of the continental United States and an 88-node set on the first set with the 50 most populated cities added.³³3Eliminating repeated cities. These numbers are from the 1990 census. Each city is also a facility, and the facility opening costs are the median property value in the city. The distances are the pairwise great-circle distances.

We then add more information to the data for our purposes. We partition the cities of the 49-node set based on the political party of the state governor at the time ($\left|C_R\right|=23,\left|C_D\right|=26$). In the 88-node set, the additional cities get their own group ($\left|C_C\right|=39$). Finally, we scale down the property values by a factor of ${10}^4$ to account for the fact that we do not incorporate the demand used in the original paper.

We evaluate our bi-criteria algorithm based on LP rounding. We compare the cost and fairness of this algorithm against classical facility location with outliers that does not enforce group-level fairness constraints. Additionally, we compare the solution costs of all algorithms to the LP optimal value for benchmarking.

We next describe the two algorithms in detail:

• $\mathrm{■}$

  LPR-F (LP Rounding with Fairness): This is our main bi-criteria algorithm. It begins by solving the fair LP relaxation with group-level outlier constraints and declares clients outliers if they are outliers to an extent of over $1-ϵ$. In the second phase, it uses the simple 4-approximation from Chudak et al. [16].

• $\mathrm{■}$

  LPR-NF (LP Rounding, Non-Fair): A baseline variant of LPR-F that does not enforce fairness. The LP includes only a single constraint on the total number of outliers. The rounding process follows as in LPR-F.

• $\mathrm{■}$

  LPH-F (LP Rounding Heuristic with Fairness): The first phase follows LPR-F. In the second phase, it applies a simple heuristic for facility location problem: facilities with fractional opening values close to 1 are opened, and each client is assigned to its nearest open facility.

• $\mathrm{■}$

  LPH-NF (LP Rounding Heuristic, Non-Fair): A variant of LPH-F that does not enforce group fairness constraints.

We define the unfairness as $\max \{{\max }_g\left\{{\mathrm{\ell }}_g^{\prime }/{\mathrm{\ell }}_g\right\},1\}$, where ${\mathrm{\ell }}_g^{\prime }$ is the number of outliers assigned to group $C_g$ by the algorithm. This definition reflects a situation in which each group is aware of its designated number of outliers and feels underrepresented when this budget is exceeded. However, a group does not experience unfairness if it is overrepresented in the covered population.

We say that an outlier budget is proportional if ${\mathrm{\ell }}_g/\left|C_g\right|\approx {\mathrm{\ell }}_h/\left|C_h\right|$ for all groups $C_g,C_h$. Similarly, we define a proportional outlier budget as one where ${\mathrm{\ell }}_g\approx \alpha \cdot \left|C_g\right|$ for all groups $C_g$ and fixed $0\le \alpha \le 1$.⁴⁴4We use $\approx$ to account for rounding issues.

• $\mathrm{■}$

  We observe in Figure 2 that the initial LP solution differentiates between “strong outliers” with $z_j$ close to 1 and “weak outliers” with $z_j$ close to 0. Moreover, the facility opening variables $y_i$ show this same bimodality. In this real-world instance, the LP produces near-integer variables, without the need for rounding, when the outlier budgets are close to proportional.

• $\mathrm{■}$

  Because the fractional variables are so close to integral in the first LP, simply rounding the facility variables in the second stage performs extremely well. In all cases, the heuristic rounding procedure exceeds the cost of the LP optimal solution by a factor of at most 1.4.

• $\mathrm{■}$

  The cost is affected by the way the per-group outliers are distributed. When the total number of outliers is fixed, moving the per-group outlier budget away from proportional increases the cost when following the budget. When the per-group budgets are close to proportional, the cost of a fair assignment is close to the cost of simply ignoring the total number of outliers. In Figure 3, this trend is demonstrated most strongly by LPR-F.

• $\mathrm{■}$

  We also observe that the algorithm without fairness can fail to provide a fair assignment while our fair algorithm consistently does. Although the bicriteria allows for violation in outliers, the $z_j$ variables tend towards integral values, so we do not violate the outlier budgets. Moreover, ensuring proportional fairness only increases the cost by a factor of 1.3 at most.

We use publicly available datasets, as preprocessed in [1]. The Adult dataset [18] contains U.S. census information, where we use the sex attribute as the group label. The Bank dataset [38] comprises data from a direct marketing campaign by a bank, with group labels based on the marital status attribute. For both datasets, we retain only the available numeric attributes, each of which is normalized independently. Due to the computational overhead of our algorithm on a non-commercial machine, we use a random subset of 500 points, and we generate a set of candidate facility locations using the $k$-means algorithm of Khandelwal et al. [33]. For all experiments, we use $k=5$.

Note that both datasets are fully unsupervised – that is, they lack ground-truth cluster labels. Consequently, we cannot directly evaluate clustering accuracy. To address this limitation, we also evaluate our algorithms on synthetic datasets with known cluster structure. The Synthetic dataset includes two group designations: “in” and “out”. In-group members are drawn from the distribution $𝒩{(0,10)}^{\otimes 2}$, while out-group members are drawn from $𝒩{(10,20)}^{\otimes 2}$. We generate 500 “in” and 50 “out” points.

For $k$-Median with fair outliers, we implement the algorithm described in Section 4 with a minor modification and compare the fairness and cost of our algorithm against two baselines for $k$-Median with outliers (non-fair). The three algorithms we evaluate are:

• $\mathrm{■}$

  R+LS-F (Reduction + Local Search, Fair): We implement the algorithm described in Section 4 with a minor modification: instead of using the primal-dual algorithm of Charikar et al. [13] for $k$-Median with penalties, we employ the local search algorithm proposed by Wang et al. [42]. The primal-dual algorithm is computationally expensive due to the use of Lagrangian relaxation; specifically, it requires solving two facility location subproblems – one using fewer than $k$ facilities and one using more – through a binary search, with each step involving a call to a facility location solver. This significantly increases the runtime in practice. In contrast the local search is efficient. The algorithm begins with an arbitrary set of $k$ open facilities and repeatedly considers swapping one currently open facility with one currently closed facility. Specifically, for each pair $(f_{\text{out}},f_{\text{in}})$ where $f_{\text{out}}$ is an open facility and $f_{\text{in}}$ is closed, it computes the cost of the solution obtained by replacing $f_{\text{out}}$ with $f_{\text{in}}$, reassigning each client to its nearest open facility. If such a swap results in a decrease in total cost of at least 1%, it is accepted. This process continues until no improving swap exists, at which point the algorithm terminates. Importantly, substituting the local search algorithm for the primal-dual method does not materially affect the worst-case approximation guarantees: the cost bound remains the same, and the violation bound increases only slightly.

• $\mathrm{■}$

  R+LS-NF (Reduction + Local Search, Non Fair) The algorithm is same as R+LS except we have no notion of group-wise fairness. The penalties are defined according to the total number of outliers. This is the algorithm for $k$-median with outlier given by Charikar et al. [13].

• $\mathrm{■}$

  LS-NF (Local Search, Non-Fair): This algorithm performs standard local search for the $k$-Median objective, starting with an arbitrary set of $k$ open facilities and repeatedly considering facility swaps as in R+LS. After convergence, the farthest $\mathrm{\ell }$ clients (based on their distances to the nearest open facility) are dropped as outliers.

We use the same unfairness metric to measure the fairness of a solution and evaluate cost as the total client-to-facility connection cost. We plot the same charts as in the facility location experiments: cost vs. percentage of outliers and unfairness vs. percentage of outliers for all three algorithms.

• $\mathrm{■}$

  The fair algorithm (R+LS-F) achieve unfairness close to 1, while the non-fair baselines R+LS-NF and LS-NF exhibit significant group-level unfairness of up to 1.12 and 1.25 for adult dataset, 1.50 and 2 for bank dataset, and 13 and 13 for synthetic dataset, respectively (see Figures 5(b), 6(b) and 7(b)).

• $\mathrm{■}$

  Enforcing fairness results in some increase in cost, it is not prohibitively large and is justified by the improved group-level guarantees (see Figures 5(a), 6(a) and 7(a)).

As with the facility location experiments in this paper and the $k$-means results of Almanza et al. [1], our findings for $k$-Median demonstrate that fairness can be achieved with no significant increase in cost.