Euclidean k-center Fair Clusterings
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912701025878016 |
|---|---|
| author | Moritaka, Ayano Nakano, Shin-ichi Tanaka, Kento Yoshida, Noriaki |
| author_facet | Moritaka, Ayano Nakano, Shin-ichi Tanaka, Kento Yoshida, Noriaki |
| contents | Many approximation algorithms and heuristic algorithms to find a fair clustering have emerged. In this paper we define a new and natural variant of fair clustering problem and design a polynomial time algorithm to compute an optimal fair clustering. Let P be a set of n points on a plane, and each point has a color in C, corresponding to a group. For each color q in C, a lower bound l(q) and an upper bound u(q) are given. Then we define the fair clustering problem as follows. The fair k-clustering problem is to find a partition of P into a set of k clusters with a minimum cost such that each cluster contains at least l(q) and at most u(q) points in P with color q. By l(q) and u(q) each cluster cannot contain too few or too many points with a specific color. If we regard a color to a gender or a minority ethnic group, the clustering corresponds to a fair clustering. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_07660 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Euclidean k-center Fair Clusterings Moritaka, Ayano Nakano, Shin-ichi Tanaka, Kento Yoshida, Noriaki Computational Geometry 68W01 Many approximation algorithms and heuristic algorithms to find a fair clustering have emerged. In this paper we define a new and natural variant of fair clustering problem and design a polynomial time algorithm to compute an optimal fair clustering. Let P be a set of n points on a plane, and each point has a color in C, corresponding to a group. For each color q in C, a lower bound l(q) and an upper bound u(q) are given. Then we define the fair clustering problem as follows. The fair k-clustering problem is to find a partition of P into a set of k clusters with a minimum cost such that each cluster contains at least l(q) and at most u(q) points in P with color q. By l(q) and u(q) each cluster cannot contain too few or too many points with a specific color. If we regard a color to a gender or a minority ethnic group, the clustering corresponds to a fair clustering. |
| title | Euclidean k-center Fair Clusterings |
| topic | Computational Geometry 68W01 |
| url | https://arxiv.org/abs/2511.07660 |