3 papers
cs.DS2026
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…
cs.DS2026
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…
cs.DS2025
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…