English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the consistent k-center clustering problem. In this problem, thegoal is to maintain a constant factor approximate $k$-center solution during asequence of $n$ point insertions and deletions while minimizing the recourse,i.e., the number of changes made to the set of centers after each pointinsertion or deletion. Previous works by Lattanzi and Vassilvitskii [ICML '12]and Fichtenberger, Lattanzi, Norouzi-Fard, and Svensson [SODA '21] showed thatin the incremental setting, where deletions are not allowed, one can obtain $k\cdot \textrm{polylog}(n) / n$ amortized recourse for both $k$-center and$k$-median, and demonstrated a matching lower bound. However, no algorithm forthe fully dynamic setting achieves less than the trivial $O(k)$ changes perupdate, which can be obtained by simply reclustering the full dataset afterevery update.  In this work, we give the first algorithm for consistent $k$-centerclustering for the fully dynamic setting, i.e., when both point insertions anddeletions are allowed, and improves upon a trivial $O(k)$ recourse bound.Specifically, our algorithm maintains a constant factor approximate solutionwhile ensuring worst-case constant recourse per update, which is optimal in thefully dynamic setting. Moreover, our algorithm is deterministic and istherefore correct even if an adaptive adversary chooses the insertions anddeletions.

Fully Dynamic Consistent $k$-Center Clustering