Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover

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(log³ 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(n^{1/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/∊²) 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.