Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover (Q6081760): Difference between revisions

@@ Property / cites work @@
+Dynamic set cover: improved algorithms and lower bounds
+Normal rank
@@ Property / cites work @@
+Q5002673
@@ Property / cites work: Q5002673 / rank @@
+Normal rank
@@ Property / cites work @@
+Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.
+Normal rank
@@ Property / cites work @@
+Fully Dynamic Maximal Matching in O (log n) Update Time
+Normal rank
@@ Property / cites work @@
+Deterministic decremental single source shortest paths: beyond the o(mn) bound
+Normal rank
@@ Property / cites work @@
+Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs
+Normal rank
@@ Property / cites work @@
+A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
+Normal rank
@@ Property / cites work @@
+Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
+Normal rank
@@ Property / cites work @@
+Design of Dynamic Algorithms via Primal-Dual Method
+Normal rank
@@ Property / cites work @@
+Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
+Normal rank
@@ Property / cites work @@
+Dynamic algorithms via the primal-dual method
@@ Property / cites work: Dynamic algorithms via the primal-dual method / rank @@
+Normal rank
@@ Property / cites work @@
+New deterministic approximation algorithms for fully dynamic matching
+Normal rank
@@ Property / cites work @@
+Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in <i>O</i>(log<sup>3</sup> <i>n</i>) Worst Case Update Time
+Normal rank
@@ Property / cites work @@
+Deterministically Maintaining a (2 + <i>∊</i>)-Approximate Minimum Vertex Cover in <i>O</i>(1/<i>∊</i><sup>2</sup>) Amortized Update Time
+Normal rank
@@ Property / cites work @@
+Q5002703
@@ Property / cites work: Q5002703 / rank @@
+Normal rank
@@ Property / cites work @@
+A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
+Normal rank
@@ Property / cites work @@
+A Greedy Heuristic for the Set-Covering Problem
@@ Property / cites work: A Greedy Heuristic for the Set-Covering Problem / rank @@
+Normal rank
@@ Property / cites work @@
+A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
+Normal rank
@@ Property / cites work @@
+Analytical approach to parallel repetition
@@ Property / cites work: Analytical approach to parallel repetition / rank @@
+Normal rank
@@ Property / cites work @@
+Online and dynamic algorithms for set cover
@@ Property / cites work: Online and dynamic algorithms for set cover / rank @@
+Normal rank
@@ Property / cites work @@
+Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
+Normal rank
@@ Property / cites work @@
+Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
+Normal rank
@@ Property / cites work @@
+Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization
+Normal rank
@@ Property / cites work @@
+Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
+Normal rank
@@ Property / cites work @@
+The cell probe complexity of dynamic range counting
+Normal rank
@@ Property / cites work @@
+Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
+Normal rank
@@ Property / cites work @@
+Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n<sup>1/2 - ε</sup>)-time
+Normal rank
@@ Property / cites work @@
+Breaking quadratic time for small vertex connectivity and an approximation scheme
+Normal rank
@@ Property / cites work @@
+Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
+Normal rank
@@ Property / cites work @@
+Maintaining a large matching and a small vertex cover
+Normal rank
@@ Property / cites work @@
+Logarithmic Lower Bounds in the Cell-Probe Model
@@ Property / cites work: Logarithmic Lower Bounds in the Cell-Probe Model / rank @@
+Normal rank
@@ Property / cites work @@
+Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
+Normal rank
@@ Property / cites work @@
+A Tight Analysis of the Greedy Algorithm for Set Cover
+Normal rank