Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
From MaRDI portal
Recommendations
- Dynamic set cover: improved algorithms and lower bounds
- Online and dynamic algorithms for set cover
- Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time
- Dynamic algorithms via the primal-dual method
- Design of dynamic algorithms via primal-dual method
Cites work
- A Greedy Heuristic for the Set-Covering Problem
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- A Tight Analysis of the Greedy Algorithm for Set Cover
- A deamortization approach for dynamic spanner and dynamic maximal matching
- A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
- Analytical approach to parallel repetition
- Breaking quadratic time for small vertex connectivity and an approximation scheme
- Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- Design of dynamic algorithms via primal-dual method
- Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
- Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
- Deterministic fully dynamic data structures for vertex cover and matching
- Deterministic partially dynamic single source shortest paths for sparse graphs
- Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time
- Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach
- Dynamic algorithms via the primal-dual method
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
- Dynamic set cover: improved algorithms and lower bounds
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
- 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.
- Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
- Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
- Logarithmic Lower Bounds in the Cell-Probe Model
- Maintaining a large matching and a small vertex cover
- New deterministic approximation algorithms for fully dynamic matching
- Online and dynamic algorithms for set cover
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- The cell probe complexity of dynamic range counting
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(6)- Dynamic set cover: improved algorithms and lower bounds
- Online and dynamic algorithms for set cover
- Dynamic algorithms via the primal-dual method
- Dynamic programming based algorithms for set multicover and multiset multicover problems
- Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.
- Design of dynamic algorithms via primal-dual method
This page was built for publication: Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081760)
