Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909630776475648 |
|---|---|
| author | Bhattacharya, Sayan Costa, Martín Farokhnejad, Ermiya Lattanzi, Silvio Parotsidis, Nikos |
| author_facet | Bhattacharya, Sayan Costa, Martín Farokhnejad, Ermiya Lattanzi, Silvio Parotsidis, Nikos |
| contents | In this paper, we consider the \emph{metric $k$-center} problem in the fully dynamic setting, where we are given a metric space $(V,d)$ evolving via a sequence of point insertions and deletions and our task is to maintain a subset $S \subseteq V$ of at most $k$ points that minimizes the objective $\max_{x \in V} \min_{y \in S}d(x, y)$. We want to design our algorithm so that we minimize its \emph{approximation ratio}, \emph{recourse} (the number of changes it makes to the solution $S$), and \emph{update time} (the time it takes to handle an update). We give a simple algorithm for dynamic $k$-center that maintains a $O(1)$-approximate solution with $O(1)$ amortized recourse and $\tilde O(k)$ amortized update time, \emph{obtaining near-optimal approximation, recourse, and update time simultaneously}. We obtain our result by combining a variant of the dynamic $k$-center algorithm of Bateni et al.~[SODA'23] with the dynamic sparsifier of Bhattacharya et al.~[NeurIPS'23]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_11470 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse Bhattacharya, Sayan Costa, Martín Farokhnejad, Ermiya Lattanzi, Silvio Parotsidis, Nikos Data Structures and Algorithms In this paper, we consider the \emph{metric $k$-center} problem in the fully dynamic setting, where we are given a metric space $(V,d)$ evolving via a sequence of point insertions and deletions and our task is to maintain a subset $S \subseteq V$ of at most $k$ points that minimizes the objective $\max_{x \in V} \min_{y \in S}d(x, y)$. We want to design our algorithm so that we minimize its \emph{approximation ratio}, \emph{recourse} (the number of changes it makes to the solution $S$), and \emph{update time} (the time it takes to handle an update). We give a simple algorithm for dynamic $k$-center that maintains a $O(1)$-approximate solution with $O(1)$ amortized recourse and $\tilde O(k)$ amortized update time, \emph{obtaining near-optimal approximation, recourse, and update time simultaneously}. We obtain our result by combining a variant of the dynamic $k$-center algorithm of Bateni et al.~[SODA'23] with the dynamic sparsifier of Bhattacharya et al.~[NeurIPS'23]. |
| title | Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.11470 |