AIConfPaper
← Search

Martin Costa

2 accepted papers

2025

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse

Sayan Bhattacharya, Martin Costa, Ermiya Farokhnejad, Silvio Lattanzi, Nikos Parotsidis
ICML 2025poster

In this paper, we consider the *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_{…

Cited by 0Source ↗PDF ↗Scholar ↗
2023

Fully Dynamic $k$-Clustering in $\tilde O(k)$ Update Time

Sayan Bhattacharya, Martin Costa, Silvio Lattanzi, Nikos Parotsidis
NeurIPS 2023poster

We present a $O(1)$-approximate fully dynamic algorithm for the $k$-median and $k$-means problems on metric spaces with amortized update time $\tilde O(k)$ and worst-case query time $\tilde O(k^2)$. We complement our theoretical analysis with the first in-depth experimental study for the dynamic $k$…

Cited by 1Source ↗PDF ↗code ↗Scholar ↗