2026-07-22T17:55:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21171 2024-09-23T09:13:18Z ddc:004 open_access

Fully Dynamic k-Means Coreset in Near-Optimal Update Time la Tour, Max Dupré Henzinger, Monika Saulpic, David clustering fully-dynamic coreset k-means We study in this paper the problem of maintaining a solution to k-median and k-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy computation of a clustering solution at query time. Our coreset algorithm has near-optimal update time of Õ(k) in general metric spaces, which reduces to Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means clustering in Euclidean space, this directly leads to an algorithm with update time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation, the query time is reduced to Õ(kd). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Max Dupré la Tour and Monika Henzinger and David Saulpic 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.100 urn:nbn:de:0030-drops-211716 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.100 eng https://creativecommons.org/licenses/by/4.0/legalcode