4 papers
Faster Randomized and Deterministic k-Clustering on Graphs
Sebastian Forster, Yasamin Nazari, Rajath Rao K. N. +1
In this paper, we study the -clustering and -center problems on graphs, where -clustering generalizes the -median () and -means () problems. We obt…
Adaptive Fully Dynamic -Center Clustering with (Near-)Optimal Worst-Case Guarantees
Mara Grilnberger, Antonis Skarlatos
Given a sequence of adversarial point insertions and point deletions, is it possible to simultaneously optimize the approximation ratio, update time, and recourse for a -cluster…
Incremental (k, z)-Clustering on Graphs
Emilio Cruciani, Sebastian Forster, Antonis Skarlatos
Given a weighted undirected graph, a number of clusters , and an exponent , the goal in the -clustering problem on graphs is to select vertices as centers that mi…
Dynamic Consistent -Center Clustering with Optimal Recourse
Sebastian Forster, Antonis Skarlatos
Given points from an arbitrary metric space and a sequence of point updates sent by an adversary, what is the minimum recourse per update (i.e., the minimum number of changes neede…