Congratulations to Mara Grilnberger and Antonis Skarlatos on the acceptance of their paper, “Adaptive Fully Dynamic k-Center Clustering with (Near-)Optimal Worst-Case Guarantees,” at the ACM-SIAM Symposium on Discrete Algorithms (SODA 2027).

The paper studies the fully dynamic k-center clustering problem, where points can be continuously inserted and deleted. The authors develop algorithms achieving a constant-factor approximation, near-optimal worst-case update time, and constant worst-case recourse, even against an adaptive adversary.

This work makes significant progress toward simultaneously achieving strong approximation, efficiency, and stability guarantees in dynamic clustering.

 Read the paper on arXiv