Dynamic \(((1+\epsilon)\ln n)\)-approximation algorithms for minimum set cover and dominating set

DOI10.1145/3564246.3585211MaRDI QIDQ6499297

Shay Solomon, Amitai Uzrad

Publication date: 8 May 2024

zbMATH Keywords

data structuresdominating setdynamic algorithmsset cover

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• 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 \)
• The Design of Approximation Algorithms
• A threshold of ln n for approximating set cover
• A Greedy Heuristic for the Set-Covering Problem
• On the hardness of approximating minimization problems
• Online and dynamic algorithms for set cover
• Optimal Bounds for the k -cut Problem
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• The Online Submodular Cover Problem
• On The Average-Case Complexity of the Bottleneck Tower of Hanoi Problem
• Dynamic set cover: improved algorithms and lower bounds
• Analytical approach to parallel repetition
• New deterministic approximation algorithms for fully dynamic matching
• Fully Dynamic Maximal Matching in O (log n) Update Time

This page was built for publication: Dynamic \(((1+\epsilon)\ln n)\)-approximation algorithms for minimum set cover and dominating set