Cover Image

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bukov, Anton, Solomon, Shay, Zhang, Tianyi
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Lossless Deamortization for Dynamic Greedy Set Cover
by: Solomon, Shay, et al.
Published: (2024)

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

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

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
by: La, An, et al.
Published: (2025)

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

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

Approximate Light Spanners in Planar Graphs
by: Le, Hung, et al.
Published: (2025)

Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $Ω(\log n)$ Lightness Barrier
by: Le, Hung, et al.
Published: (2023)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

A Nearly Quadratic-Time FPTAS for Knapsack
by: Chen, Lin, et al.
Published: (2023)

0-1 Knapsack in Nearly Quadratic Time
by: Jin, Ce
Published: (2023)

Knapsack with Small Items in Near-Quadratic Time
by: Bringmann, Karl
Published: (2023)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
by: Mao, Xiao
Published: (2023)

Breaking the Barrier $2^k$ for Subset Feedback Vertex Set in Chordal Graphs
by: Bai, Tian, et al.
Published: (2022)

Towards Instance-Optimal Euclidean Spanners
by: Le, Hung, et al.
Published: (2024)

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

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)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Tree-Like Shortcuttings of Trees
by: Le, Hung, et al.
Published: (2025)

Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
by: Le, Hung, et al.
Published: (2021)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
by: Chuzhoy, Julia, et al.
Published: (2025)

Engineering Algorithms for Dynamic Greedy Set Cover
by: Uzrad, Amitai
Published: (2026)

Dynamic Pricing Algorithms for Online Set Cover
by: Bender, Max, et al.
Published: (2024)

A Nearly Quadratic Improvement for Memory Reallocation
by: Farach-Colton, Martin, et al.
Published: (2024)

Almost-Optimal Sublinear Additive Spanners
by: Tan, Zihan, et al.
Published: (2023)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
by: Boneh, Itai, et al.
Published: (2025)

Time-Optimal Construction of String Synchronizing Sets
by: Ellert, Jonas, et al.
Published: (2026)

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

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

Optimal Neighborhood Exploration for Dynamic Independent Sets
by: Borowitz, Jannick, et al.
Published: (2024)

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

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
by: Bhattacharya, Sayan, et al.
Published: (2023)

Deterministic Longest Common Subsequence Approximation in Near-Linear Time
by: Boneh, Itai, et al.
Published: (2025)

Fair Set Cover
by: Dehghankar, Mohsen, et al.
Published: (2024)

Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut
by: Baswana, Surender, et al.
Published: (2025)