Lune

SODA2025Top-tier venue

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-f Time Barrier

Anton Bukov, Shay Solomon, Tianyi Zhang

Abstract

The dynamic set cover problem has been subject to extensive research since the pioneering works of [BHI, ICALP'15] and [GKKP17, STOC'17]. The input is a set system (U, S) on a fixed collection S of sets and a dynamic universe of elements, where each element appears in a most f sets and the cost of each set lies in the range [1/C, 1]; the ultimate goal is to maintain a set cover under insertions and deletions of elements, with optimal bounds on both the approximation factor and the update time.

Most previous works considers the low-frequency regime, namely f = O(log n), and this line of work has culminated with a deterministic (1 + ϵ)f -approximation algorithm with amortized update time O( f 2 ϵ 3 + f ϵ 2 log C) [BHNW, SODA'21] and a randomized f -approximation algorithm against an oblivious adversary with expected amortized update time O(f 2 ) for the unweighted case [AS, ESA'21]. In the high-frequency regime of f = Ω(log n), an O(log n)-approximation algorithm with amortized update time O(f log n) was given by [GKKP17, STOC'17], and recently [SU, STOC'23] showed that the same update time of O(f log n) suffices for achieving approximation (1 + ϵ) ln n.

Interestingly, at the intersection of the two regimes, i.e., f = Θ(log n), the state-of-the-art results coincide (ignoring the dependencies on ϵ and C): approximation Θ(f ) = Θ(log n) with amortized update time O(f 2 ) = O(f log n) = O(log 2 n). Up to this date, no previous work achieved update time of o(f 2 ), even allowing randomization against an oblivious adversary and even for a worse approximation guarantee.

In this paper we break the Ω(f 2 ) update time barrier via the following results:

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

3 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set cites Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
  • Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time cites Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
  • A Lossless Deamortization for Dynamic Greedy Set Cover cites Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set
  • A Lossless Deamortization for Dynamic Greedy Set Cover cites Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
  • Fully Dynamic Set Cover: Worst-Case Recourse and Update Time cites Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set
  • Fully Dynamic Set Cover: Worst-Case Recourse and Update Time cites A Lossless Deamortization for Dynamic Greedy Set Cover
  • Fully Dynamic Set Cover: Worst-Case Recourse and Update Time cites Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. A Lossless Deamortization for Dynamic Greedy Set CoverShay Solomon, Amitai Uzrad, Tianyi ZhangFOCS 2024 · 5 citations
  2. Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating SetShay Solomon, Amitai UzradSTOC 2023 · 3 citations
  3. Fully Dynamic Set Cover: Worst-Case Recourse and Update TimeSayan Bhattacharya, Ruoxu Cen, Debmalya PanigrahiSTOC 2026 · 3 citations

Builds on3

  1. Dynamic Set Cover: Improved Amortized and Worst-Case Update TimeSayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei WuSODA 2021 · 8 citations
  2. Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal TimeSayan Bhattacharya, Martín Costa, Nadav Panski, Shay SolomonSODA 2024 · 6 citations
  3. Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating SetShay Solomon, Amitai UzradSTOC 2023 · 3 citations

Related papers

  1. Dynamic Geometric Set Cover, RevisitedTimothy M. Chan, Qizheng He, Subhash Suri, Jie XueSODA 2022 · 4 citations
  2. Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight UpdatesSayan Bhattacharya, Peter Kiss, Thatchaphol SaranurakSODA 2023 · 9 citations
  3. A Dynamic Algorithm for Weighted Submodular Cover ProblemKiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade et al.ICML 2024 · 2 citations
  4. Fully-Dynamic Submodular Cover with Bounded RecourseAnupam Gupta, Roie LevinFOCS 2020 · 8 citations
  5. A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest PathsJulia Chuzhoy, Ruimin ZhangSTOC 2023 · 7 citations
Dusk over the sea between two cliffs drawn in fine vertical lines