Individual Fairness in Graph Decomposition
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917681745100800 |
|---|---|
| author | Munagala, Kamesh Sankar, Govind S. |
| author_facet | Munagala, Kamesh Sankar, Govind S. |
| contents | In this paper, we consider classic randomized low diameter decomposition procedures for planar graphs that obtain connected clusters which are cohesive in that close-by pairs of nodes are assigned to the same cluster with high probability. We require the additional aspect of individual fairness - pairs of nodes at comparable distances should be separated with comparable probability. We show that classic decomposition procedures do not satisfy this property. We present novel algorithms that achieve various trade-offs between this property and additional desiderata of connectivity of the clusters and optimality in the number of clusters. We show that our individual fairness bounds may be difficult to improve by tying the improvement to resolving a major open question in metric embeddings. We finally show the efficacy of our algorithms on real planar networks modeling congressional redistricting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00213 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Individual Fairness in Graph Decomposition Munagala, Kamesh Sankar, Govind S. Data Structures and Algorithms In this paper, we consider classic randomized low diameter decomposition procedures for planar graphs that obtain connected clusters which are cohesive in that close-by pairs of nodes are assigned to the same cluster with high probability. We require the additional aspect of individual fairness - pairs of nodes at comparable distances should be separated with comparable probability. We show that classic decomposition procedures do not satisfy this property. We present novel algorithms that achieve various trade-offs between this property and additional desiderata of connectivity of the clusters and optimality in the number of clusters. We show that our individual fairness bounds may be difficult to improve by tying the improvement to resolving a major open question in metric embeddings. We finally show the efficacy of our algorithms on real planar networks modeling congressional redistricting. |
| title | Individual Fairness in Graph Decomposition |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.00213 |