Facility Location and $k$-Median with Fair Outliers
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909720979177472 |
|---|---|
| author | Dabas, Rajni Khuller, Samir Rivkin, Emilie |
| author_facet | Dabas, Rajni Khuller, Samir Rivkin, Emilie |
| contents | Classical clustering problems such as \emph{Facility Location} and \emph{$k$-Median} aim to efficiently serve a set of clients from a subset of facilities -- minimizing the total cost of facility openings and client assignments in Facility Location, and minimizing assignment (service) cost under a facility count constraint in $k$-Median. These problems are highly sensitive to outliers, and therefore researchers have studied variants that allow excluding a small number of clients as outliers to reduce cost. However, in many real-world settings, clients belong to different demographic or functional groups, and unconstrained outlier removal can disproportionately exclude certain groups, raising fairness concerns.
We study \emph{Facility Location with Fair Outliers}, where each group is allowed a specified number of outliers, and the objective is to minimize total cost while respecting group-wise fairness constraints. We present a bicriteria approximation with a $O(1/ε)$ approximation factor and $(1+ 2ε)$ factor violation in outliers per group. For \emph{$k$-Median with Fair Outliers}, we design a bicriteria approximation with a $4(1+ω/ε)$ approximation factor and $(ω+ ε)$ violation in outliers per group improving on prior work by avoiding dependence on $k$ in outlier violations. We also prove that the problems are W[1]-hard parameterized by $ω$, assuming the Exponential Time Hypothesis.
We complement our algorithmic contributions with a detailed empirical analysis, demonstrating that fairness can be achieved with negligible increase in cost and that the integrality gap of the standard LP is small in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02572 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Facility Location and $k$-Median with Fair Outliers Dabas, Rajni Khuller, Samir Rivkin, Emilie Data Structures and Algorithms Classical clustering problems such as \emph{Facility Location} and \emph{$k$-Median} aim to efficiently serve a set of clients from a subset of facilities -- minimizing the total cost of facility openings and client assignments in Facility Location, and minimizing assignment (service) cost under a facility count constraint in $k$-Median. These problems are highly sensitive to outliers, and therefore researchers have studied variants that allow excluding a small number of clients as outliers to reduce cost. However, in many real-world settings, clients belong to different demographic or functional groups, and unconstrained outlier removal can disproportionately exclude certain groups, raising fairness concerns. We study \emph{Facility Location with Fair Outliers}, where each group is allowed a specified number of outliers, and the objective is to minimize total cost while respecting group-wise fairness constraints. We present a bicriteria approximation with a $O(1/ε)$ approximation factor and $(1+ 2ε)$ factor violation in outliers per group. For \emph{$k$-Median with Fair Outliers}, we design a bicriteria approximation with a $4(1+ω/ε)$ approximation factor and $(ω+ ε)$ violation in outliers per group improving on prior work by avoiding dependence on $k$ in outlier violations. We also prove that the problems are W[1]-hard parameterized by $ω$, assuming the Exponential Time Hypothesis. We complement our algorithmic contributions with a detailed empirical analysis, demonstrating that fairness can be achieved with negligible increase in cost and that the integrality gap of the standard LP is small in practice. |
| title | Facility Location and $k$-Median with Fair Outliers |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.02572 |