Fair Center Clustering in Sliding Windows
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913724455976960 |
|---|---|
| author | Ceccarello, Matteo Pietracaprina, Andrea Pucci, Geppino Visonà, Francesco |
| author_facet | Ceccarello, Matteo Pietracaprina, Andrea Pucci, Geppino Visonà, Francesco |
| contents | The $k$-center problem requires the selection of $k$ points (centers) from a given metric pointset $W$ so to minimize the maximum distance of any point of $W$ from the closest center. This paper focuses on a fair variant of the problem, known as \emph {fair center}, where each input point belongs to some category and each category may contribute a limited number of points to the center set. We present the first space-efficient streaming algorithm for fair center in general metrics, under the sliding window model. At any time $t$, the algorithm is able to provide a solution for the current window whose quality is almost as good as the one guaranteed by the best, polynomial-time sequential algorithms run on the entire window, and exhibits space and time requirements independent of the window size. Our theoretical results are backed by an extensive set of experiments on both real-world and synthetic datasets, which provide evidence of the practical viability of the algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_05260 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fair Center Clustering in Sliding Windows Ceccarello, Matteo Pietracaprina, Andrea Pucci, Geppino Visonà, Francesco Data Structures and Algorithms The $k$-center problem requires the selection of $k$ points (centers) from a given metric pointset $W$ so to minimize the maximum distance of any point of $W$ from the closest center. This paper focuses on a fair variant of the problem, known as \emph {fair center}, where each input point belongs to some category and each category may contribute a limited number of points to the center set. We present the first space-efficient streaming algorithm for fair center in general metrics, under the sliding window model. At any time $t$, the algorithm is able to provide a solution for the current window whose quality is almost as good as the one guaranteed by the best, polynomial-time sequential algorithms run on the entire window, and exhibits space and time requirements independent of the window size. Our theoretical results are backed by an extensive set of experiments on both real-world and synthetic datasets, which provide evidence of the practical viability of the algorithm. |
| title | Fair Center Clustering in Sliding Windows |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.05260 |