Cover Image

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Grilnberger, Mara, Skarlatos, Antonis
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Dynamic Consistent $k$-Center Clustering with Optimal Recourse
by: Forster, Sebastian, et al.
Published: (2024)

Incremental (k, z)-Clustering on Graphs
by: Cruciani, Emilio, et al.
Published: (2026)

Dynamic Matroids: Base Packing and Covering
by: de Vos, Tijn, et al.
Published: (2025)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

A Weighted-to-Unweighted Reduction for Matroid Intersection
by: Dudeja, Aditi, et al.
Published: (2026)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
by: Navarro, Gonzalo
Published: (2024)

Dynamic algorithms for k-center on graphs
by: Cruciani, Emilio, et al.
Published: (2023)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
by: Ghaffari, Mohsen, et al.
Published: (2025)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
by: Mao, Xiao
Published: (2023)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
by: la Tour, Max Dupré, et al.
Published: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
by: Bhattacharya, Sayan, et al.
Published: (2025)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
by: Bansal, Nikhil, et al.
Published: (2024)

Deterministic $k$-Median Clustering in Near-Optimal Time
by: Costa, Martín, et al.
Published: (2025)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Dynamic Set Cover with Worst-Case Recourse
by: Solomon, Shay, et al.
Published: (2025)

Optimal Static Dictionary with Worst-Case Constant Query Time
by: Hu, Yang, et al.
Published: (2024)

On Parallel $k$-Center Clustering
by: Coy, Sam, et al.
Published: (2023)

Fully Dynamic Euclidean k-Means
by: Bhattacharya, Sayan, et al.
Published: (2025)

Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
by: Manthey, Bodo, et al.
Published: (2023)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
by: Meierhans, Simon, et al.
Published: (2025)

Dynamic Data Layout Optimization with Worst-case Guarantees
by: Rong, Kexin, et al.
Published: (2024)

Moderate Dimension Reduction for $k$-Center Clustering
by: Jiang, Shaofeng H. -C., et al.
Published: (2023)

Maximal Biclique Enumeration with Improved Worst-Case Time Complexity Guarantee: A Partition-Oriented Strategy
by: Wang, Kaixin, et al.
Published: (2026)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
by: Abboud, Amir, et al.
Published: (2024)

Online Metric Matching: Beyond the Worst Case
by: Yang, Mingwei, et al.
Published: (2024)

Beyond Worst Case Local Computation Algorithms
by: Biswas, Amartya Shankha, et al.
Published: (2024)

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
by: El-Hayek, Antoine, et al.
Published: (2023)

Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space
by: Jang, Jihoon, et al.
Published: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
by: Haeupler, Bernhard, et al.
Published: (2024)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
by: Sawettamalya, Pachara, et al.
Published: (2025)

DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering
by: Yu, Shangdi, et al.
Published: (2025)

Hybrid k-Clustering: Blending k-Median and k-Center
by: Fomin, Fedor V., et al.
Published: (2024)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
by: Meierhans, Simon, et al.
Published: (2025)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
by: Black, Hadley
Published: (2023)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
by: Behnezhad, Soheil, et al.
Published: (2024)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Maintaining $k$-MinHash Signatures over Fully-Dynamic Data Streams with Recovery
by: Clementi, Andrea, et al.
Published: (2024)

Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
by: van der Hoog, Ivor, et al.
Published: (2025)