Buchumschlag

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bhattacharya, Sayan, Costa, Martín, Garg, Naveen, Lattanzi, Silvio, Parotsidis, Nikos
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

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

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

Dynamic Correlation Clustering in Sublinear Update Time
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2024)

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

DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering
von: Yu, Shangdi, et al.
Veröffentlicht: (2025)

Fully Dynamic Algorithms for Transitive Reduction
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

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

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
von: Georgiadis, Loukas, et al.
Veröffentlicht: (2026)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Fully-Dynamic Submodular Cover with Bounded Recourse
von: Gupta, Anupam, et al.
Veröffentlicht: (2020)

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

Dynamic Consistent $k$-Center Clustering with Optimal Recourse
von: Forster, Sebastian, et al.
Veröffentlicht: (2024)

The Cost of Consistency: Submodular Maximization with Constant Recourse
von: Dütting, Paul, et al.
Veröffentlicht: (2024)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
von: Meierhans, Simon, et al.
Veröffentlicht: (2025)

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

Fully Dynamic Submodular Maximization over Matroids
von: Dütting, Paul, et al.
Veröffentlicht: (2023)

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

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

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

Vizing's Theorem in Near-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Arboricity-Dependent Algorithms for Edge Coloring
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

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

Spectral Clustering with Side Information
von: Fichtenberger, Hendrik, et al.
Veröffentlicht: (2025)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2026)

A Simple Algorithm for Dynamic Carpooling with Recourse
von: Efron, Yuval, et al.
Veröffentlicht: (2024)

Dynamic Set Cover with Worst-Case Recourse
von: Solomon, Shay, et al.
Veröffentlicht: (2025)

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

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
von: Kapralov, Michael, et al.
Veröffentlicht: (2022)

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
von: Sadeh, Yaniv, et al.
Veröffentlicht: (2026)

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
von: Nezhad, Sina Bagheri, et al.
Veröffentlicht: (2025)

Online Steiner Forest with Recourse
von: Long, Yaowei, et al.
Veröffentlicht: (2026)

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

Almost Tight Bounds for Differentially Private Densest Subgraph
von: Dinitz, Michael, et al.
Veröffentlicht: (2023)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Clustering with Label Consistency
von: Chakraborty, Diptarka, et al.
Veröffentlicht: (2025)