On the Advice Complexity of Online Unit Clustering
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912046752202752 |
|---|---|
| author | Nagy-György, Judit |
| author_facet | Nagy-György, Judit |
| contents | In online unit clustering, points of a metric space arriving one by one must be partitioned into clusters of diameter at most 1, where the cost is the number of clusters.
This paper gives linear upper and lower bounds on the advice complexity of 1-competitive online unit clustering algorithms, in terms of the number of points in $\mathbb{R}^d$ and $\mathbb{Z}^d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_14730 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Advice Complexity of Online Unit Clustering Nagy-György, Judit Data Structures and Algorithms 68W27 In online unit clustering, points of a metric space arriving one by one must be partitioned into clusters of diameter at most 1, where the cost is the number of clusters. This paper gives linear upper and lower bounds on the advice complexity of 1-competitive online unit clustering algorithms, in terms of the number of points in $\mathbb{R}^d$ and $\mathbb{Z}^d$. |
| title | On the Advice Complexity of Online Unit Clustering |
| topic | Data Structures and Algorithms 68W27 |
| url | https://arxiv.org/abs/2309.14730 |