Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915420904095744 |
|---|---|
| author | Nezhad, Sina Bagheri Bandyapadhyay, Sayan Chen, Tianzhi |
| author_facet | Nezhad, Sina Bagheri Bandyapadhyay, Sayan Chen, Tianzhi |
| contents | In a seminal work, Chierichetti et al. introduced the $(t,k)$-fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called fair if the number of red points in each cluster is at most $t$ times and at least $1/t$ times the number of blue points in that cluster. The goal is to compute a fair clustering with at most $k$ clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time $O(1)$- and $O(t)$-approximation for the $k$-center and the $k$-median objective, respectively. Recently, Carta et al. studied this problem with the sum-of-radii objective and obtained a $(6+ε)$-approximation with running time $O((k\log_{1+ε}(k/ε))^kn^{O(1)})$, i.e., fixed-parameter tractable in $k$. Here $n$ is the input size. In this work, we design the first polynomial-time $O(1)$-approximation for $(t,k)$-fair clustering with the sum-of-radii objective, improving the result of Carta et al. Our result places sum-of-radii in the same group of objectives as $k$-center, that admit polynomial-time $O(1)$-approximations. This result also implies a polynomial-time $O(1)$-approximation for the Euclidean version of the problem, for which an $f(k)\cdot n^{O(1)}$-time $(1+ε)$-approximation was known due to Drexler et al.. Here $f$ is an exponential function of $k$. We are also able to extend our result to any arbitrary $\ell\ge 2$ number of colors when $t=1$. This matches known results for the $k$-center and $k$-median objectives in this case. The significant disparity of sum-of-radii compared to $k$-center and $k$-median presents several complex challenges, all of which we successfully overcome in our work. Our main contribution is a novel cluster-merging-based analysis technique for sum-of-radii that helps us achieve the constant-approximation bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14683 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering Nezhad, Sina Bagheri Bandyapadhyay, Sayan Chen, Tianzhi Data Structures and Algorithms In a seminal work, Chierichetti et al. introduced the $(t,k)$-fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called fair if the number of red points in each cluster is at most $t$ times and at least $1/t$ times the number of blue points in that cluster. The goal is to compute a fair clustering with at most $k$ clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time $O(1)$- and $O(t)$-approximation for the $k$-center and the $k$-median objective, respectively. Recently, Carta et al. studied this problem with the sum-of-radii objective and obtained a $(6+ε)$-approximation with running time $O((k\log_{1+ε}(k/ε))^kn^{O(1)})$, i.e., fixed-parameter tractable in $k$. Here $n$ is the input size. In this work, we design the first polynomial-time $O(1)$-approximation for $(t,k)$-fair clustering with the sum-of-radii objective, improving the result of Carta et al. Our result places sum-of-radii in the same group of objectives as $k$-center, that admit polynomial-time $O(1)$-approximations. This result also implies a polynomial-time $O(1)$-approximation for the Euclidean version of the problem, for which an $f(k)\cdot n^{O(1)}$-time $(1+ε)$-approximation was known due to Drexler et al.. Here $f$ is an exponential function of $k$. We are also able to extend our result to any arbitrary $\ell\ge 2$ number of colors when $t=1$. This matches known results for the $k$-center and $k$-median objectives in this case. The significant disparity of sum-of-radii compared to $k$-center and $k$-median presents several complex challenges, all of which we successfully overcome in our work. Our main contribution is a novel cluster-merging-based analysis technique for sum-of-radii that helps us achieve the constant-approximation bounds. |
| title | Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.14683 |