Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
From MaRDI portal
Publication:6081760
DOI10.1137/21m1428649zbMath1523.68171MaRDI QIDQ6081760
Xiaowei Wu, Monika R. Henzinger, Sayan Bhattacharya, Danupon Nanongkai
Publication date: 26 October 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
90C59: Approximation methods and heuristics in mathematical programming
68P05: Data structures
68W25: Approximation algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Dynamic algorithms via the primal-dual method
- Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization
- Maintaining a large matching and a small vertex cover
- Design of Dynamic Algorithms via Primal-Dual Method
- A Greedy Heuristic for the Set-Covering Problem
- A Tight Analysis of the Greedy Algorithm for Set Cover
- Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
- Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs
- Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
- Online and dynamic algorithms for set cover
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time
- Dynamic set cover: improved algorithms and lower bounds
- Breaking quadratic time for small vertex connectivity and an approximation scheme
- A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
- Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
- Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time
- A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
- Analytical approach to parallel repetition
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Deterministic decremental single source shortest paths: beyond the o(mn) bound
- New deterministic approximation algorithms for fully dynamic matching
- Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
- The cell probe complexity of dynamic range counting
- Logarithmic Lower Bounds in the Cell-Probe Model
- Fully Dynamic Maximal Matching in O (log n) Update Time
- Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.