Buchumschlag

Fully Dynamic k-Means Coreset in Near-Optimal Update Time

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	la Tour, Max Dupré, Henzinger, Monika, Saulpic, David
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means
von: la Tour, Max Dupré, et al.
Veröffentlicht: (2024)

Making Old Things New: A Unified Algorithm for Differentially Private Clustering
von: la Tour, Max Dupré, et al.
Veröffentlicht: (2024)

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

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
von: El-Hayek, Antoine, et al.
Veröffentlicht: (2023)

Improved Lower Bounds for Privacy under Continual Release
von: Aryanfard, Bardiya, et al.
Veröffentlicht: (2025)

Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
von: El-Hayek, Antoine, et al.
Veröffentlicht: (2024)

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
von: Henzinger, Monika, et al.
Veröffentlicht: (2025)

Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
von: El-Hayek, Antoine, et al.
Veröffentlicht: (2025)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
von: Goranci, Gramoz, et al.
Veröffentlicht: (2023)

Near-Optimal Generalized Private Testing
von: Chaturvedi, Anamay, et al.
Veröffentlicht: (2026)

Near-Optimal Bounds for Parameterized Euclidean k-means
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
von: Henzinger, Monika, et al.
Veröffentlicht: (2024)

Fully Dynamic Euclidean k-Means
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2025)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Nearly Optimal Attention Coresets
von: Liberty, Edo, et al.
Veröffentlicht: (2026)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
von: Grilnberger, Mara, et al.
Veröffentlicht: (2026)

Improved Differentially Private Continual Observation Using Group Algebra
von: Henzinger, Monika, et al.
Veröffentlicht: (2024)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
von: Mao, Xiao
Veröffentlicht: (2023)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
von: Huang, Lingxiao, et al.
Veröffentlicht: (2022)

Efficient Contractions of Dynamic Graphs -- with Applications
von: Henzinger, Monika, et al.
Veröffentlicht: (2025)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
von: Zheng, Da Wei, et al.
Veröffentlicht: (2023)

Deterministic $k$-Median Clustering in Near-Optimal Time
von: Costa, Martín, et al.
Veröffentlicht: (2025)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
von: Axiotis, Kyriakos, et al.
Veröffentlicht: (2024)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2025)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
von: Draganov, Andrew, et al.
Veröffentlicht: (2024)

Round-efficient Fully-scalable MPC algorithms for k-Means
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2026)

Concurrent Composition for Differentially Private Continual Mechanisms
von: Henzinger, Monika, et al.
Veröffentlicht: (2024)

Dynamic Hierarchical $j$-Tree Decomposition and Its Applications
von: Goranci, Gramoz, et al.
Veröffentlicht: (2026)

Dynamically Maintaining the Persistent Homology of Time Series
von: di Montesano, Sebastiano Cultrera, et al.
Veröffentlicht: (2023)

Transposition is Nearly Optimal for IID List Update
von: Coester, Christian
Veröffentlicht: (2026)

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
von: Dhulipala, Laxman, et al.
Veröffentlicht: (2025)

Gerrymandering Planar Graphs
von: Dippel, Jack, et al.
Veröffentlicht: (2023)

Time-Optimal $k$-Server
von: Frei, Fabian, et al.
Veröffentlicht: (2025)

Coresets for Kernel Clustering
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2021)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
von: Braverman, Vladimir, et al.
Veröffentlicht: (2024)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
von: Sawettamalya, Pachara, et al.
Veröffentlicht: (2025)