Image de couverture de livre

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bhattacharya, Sayan, Cen, Ruoxu, Panigrahi, Debmalya
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Network Unreliability in Almost-Linear Time
par: Cen, Ruoxu, et autres
Publié: (2025)

Hypergraph Unreliability in Quasi-Polynomial Time
par: Cen, Ruoxu, et autres
Publié: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
par: Bhattacharya, Sayan, et autres
Publié: (2024)

Dynamic Set Cover with Worst-Case Recourse
par: Solomon, Shay, et autres
Publié: (2025)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
par: Bhattacharya, Sayan, et autres
Publié: (2024)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
par: Meierhans, Simon, et autres
Publié: (2025)

Fast Algorithms for Graph Arboricity and Related Problems
par: Cen, Ruoxu, et autres
Publié: (2025)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
par: Bhattacharya, Sayan, et autres
Publié: (2024)

Fully-Dynamic Submodular Cover with Bounded Recourse
par: Gupta, Anupam, et autres
Publié: (2020)

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

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
par: Meierhans, Simon, et autres
Publié: (2025)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
par: Bhattacharya, Sayan, et autres
Publié: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
par: Bernstein, Aaron, et autres
Publié: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
par: Haeupler, Bernhard, et autres
Publié: (2024)

Nearly Tight Bounds for the Online Sorting Problem
par: Azar, Yossi, et autres
Publié: (2025)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
par: Grilnberger, Mara, et autres
Publié: (2026)

Fully Dynamic Euclidean k-Means
par: Bhattacharya, Sayan, et autres
Publié: (2025)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
par: Navarro, Gonzalo
Publié: (2024)

Count-Min Sketch with Conservative Updates: Worst-Case Analysis
par: Mazziane, Younes Ben, et autres
Publié: (2024)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
par: Goranci, Gramoz, et autres
Publié: (2025)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
par: la Tour, Max Dupré, et autres
Publié: (2024)

Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
par: van der Hoog, Ivor, et autres
Publié: (2025)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
par: Bhattacharya, Sayan, et autres
Publié: (2026)

Language Generation in the Limit: Noise, Loss, and Feedback
par: Bai, Yannan, et autres
Publié: (2025)

A Simple Algorithm for Dynamic Carpooling with Recourse
par: Efron, Yuval, et autres
Publié: (2024)

Optimal Static Dictionary with Worst-Case Constant Query Time
par: Hu, Yang, et autres
Publié: (2024)

An Optimal Algorithm for Stochastic Vertex Cover
par: Brand, Jan van den, et autres
Publié: (2026)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
par: Ghaffari, Mohsen, et autres
Publié: (2025)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
par: Bhattacharya, Sayan, et autres
Publié: (2023)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
par: Abboud, Amir, et autres
Publié: (2024)

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
par: Sadeh, Yaniv, et autres
Publié: (2026)

Deterministic Almost-Linear-Time Gomory-Hu Trees
par: Abboud, Amir, et autres
Publié: (2025)

Online Metric Matching: Beyond the Worst Case
par: Yang, Mingwei, et autres
Publié: (2024)

Beyond Worst Case Local Computation Algorithms
par: Biswas, Amartya Shankha, et autres
Publié: (2024)

Online Steiner Forest with Recourse
par: Long, Yaowei, et autres
Publié: (2026)

Learning-Augmented Algorithms for $k$-median via Online Learning
par: Hebbar, Anish, et autres
Publié: (2026)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
par: Mitrović, Slobodan, et autres
Publié: (2026)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
par: Braverman, Vladimir, et autres
Publié: (2024)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
par: Bernstein, Aaron, et autres
Publié: (2025)

All-Pairs Suffix-Prefix on Fully Dynamic Set of Strings
par: Kikuchi, Masaru, et autres
Publié: (2024)