# A Lossless Deamortization for Dynamic Greedy Set Cover 111A preliminary
version of this paper was accepted to the proceedings of FOCS 2024.

Shay Solomon Funded by the European Union (ERC, DynOpt, 101043159). Views and
opinions expressed are however those of the author(s) only and do not
necessarily reflect those of the European Union or the European Research
Council. Neither the European Union nor the granting authority can be held
responsible for them. This research was also supported by the Israel Science
Foundation (ISF) grant No.1991/1, and by a grant from the United States-Israel
Binational Science Foundation (BSF), Jerusalem, Israel, and the United States
National Science Foundation (NSF). Tel Aviv University  Amitai Uzrad Funded by
the European Union (ERC, DynOpt, 101043159). Views and opinions expressed are
however those of the author(s) only and do not necessarily reflect those of
the European Union or the European Research Council. Neither the European
Union nor the granting authority can be held responsible for them. This
research was also supported by the Israel Science Foundation (ISF) grant
No.1991/1. Tel Aviv University  Tianyi Zhang Funded by the European Union
(ERC, DynOpt, 101043159). Views and opinions expressed are however those of
the author(s) only and do not necessarily reflect those of the European Union
or the European Research Council. Neither the European Union nor the granting
authority can be held responsible for them. Tel Aviv University

The dynamic set cover problem has been subject to growing research attention
in recent years. In this problem, we are given as input a dynamic universe of
at most $n$ elements and a fixed collection of $m$ sets, where each element
appears in a most $f$ sets and the cost of each set is in $[1/C,1]$, and the
goal is to efficiently maintain an approximate minimum set cover under element
updates.

Two algorithms that dynamize the classic _greedy_ algorithm are known,
providing $O(\log n)$ and $((1+\epsilon)\ln n)$-approximation with amortized
update times $O(f\log n)$ and $O(\frac{f\log n}{\epsilon^{5}})$, respectively
[GKKP (STOC’17); SU (STOC’23)]. The question of whether one can get
approximation $O(\log n)$ (or even worse) with low _worst-case_ update time
has remained open — _only the naive $O(f\cdot n)$ time bound is known_, even
for unweighted instances.

In this work we devise the first amortized greedy algorithm that is amenable
to an efficient deamortization, and also develop a lossless deamortization
approach suitable for the set cover problem, the combination of which yields a
$((1+\epsilon)\ln n)$-approximation algorithm with a worst-case update time of
$O\left(\frac{f\log n}{\epsilon^{2}}\right)$. _Our worst-case time bound — the
first to break the naive $O(f\cdot n)$ bound — matches the previous best
amortized bound, and actually improves its $\epsilon$-dependence_.

Further, to demonstrate the applicability of our deamortization approach, we
employ it, in conjunction with the primal-dual amortized algorithm of [BHN
(FOCS’19)], to obtain a $((1+\epsilon)f)$-approximation algorithm with a
worst-case update time of $O\left(\frac{f\log n}{\epsilon^{2}}\right)$,
improving over the previous best bound of
$O(\frac{f\cdot\log^{2}(Cn)}{\epsilon^{3}})$ [BHNW (SODA’21)].

Finally, as direct implications of our results for set cover, we (i) achieve
the first nontrivial worst-case update time for the _dominating set_ problem,
and (ii) improve the state-of-the-art worst-case update time for the _vertex
cover_ problem.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contribution
  2. 2 Technical Overview
    1. 2.1 The Known Amortized Algorithms
      1. 2.1.1 The Fully Local Approach
      2. 2.1.2 The Partially Global Approach: From $O(\log n)$ to $(1+\epsilon)\ln n$ Approximation
    2. 2.2 Our Approach
      1. 2.2.1 A Fully Global Amortized Algorithm
      2. 2.2.2 A Lossless Deamortization
  3. 3 Our Algorithm I: Aspect Ratio Dependence in Update Time
    1. 3.1 Preliminaries, Invariants and Approximation Factor Analysis
    2. 3.2 Algorithm Description
      1. 3.2.1 Foreground
      2. 3.2.2 Background
    3. 3.3 Implementation Details and Update Time Analysis
      1. 3.3.1 Foreground Operations
      2. 3.3.2 Reset - Initialization Phase
      3. 3.3.3 Reset - Greedy Set Cover Algorithm Phase
      4. 3.3.4 Reset - Termination Phase
    4. 3.4 Proof of Correctness
  4. 4 Removing Dependency on Aspect Ratio
    1. 4.1 Preliminaries and Basic Data Structures
    2. 4.2 Algorithm Description
  5. 5 Extension to the Low-Frequency Regime
    1. 5.1 Preliminaries and Invariants
    2. 5.2 Algorithm Description and Update Time Analysis
      1. 5.2.1 Foreground
      2. 5.2.2 Foreground and Background Data Structures
      3. 5.2.3 Background
    3. 5.3 Proof of Correctness
    4. 5.4 Removing Dependency on Aspect Ratio
  6. 6 From Dynamic Dominating Set to Set Cover
    1. 6.1 A Reduction in the Dynamic Setting

##  1 Introduction

In the classical set cover problem, the input is a set system
$(\mathcal{U},\mathcal{S})$, where $\mathcal{U}$ is a universe of $n$ elements
and $\mathcal{S}$ is a family of $m$ sets $s\in\mathcal{S}$ of elements in
$\mathcal{U}$, each with a cost $\mathsf{cost}(s)\in[\frac{1}{C},1]$. The
frequency $f$ of the set system $(\mathcal{U},\mathcal{S})$ is the largest
number of sets in $\mathcal{S}$ that any element in $\mathcal{U}$ can possibly
belong to. A subset of sets $\mathcal{S}^{\prime}\subseteq\mathcal{S}$ is
called a set cover of $\mathcal{U}$ if every element in $\mathcal{U}$ resides
in at least one set in $\mathcal{S}^{\prime}$. The basic goal is to compute a
minimum set cover, i.e., a set cover $\mathcal{S}^{*}\subseteq\mathcal{S}$
whose total cost
$\mathsf{cost}(\mathcal{S}^{*})=\sum_{s\in\mathcal{S}^{*}}\mathsf{cost}(s)$ is
minimized. A well-known greedy algorithm achieves a $(\ln n)$-approximation,
and using a primal-dual approach one can obtain an $f$-approximation; these
two approaches are believed to be optimal, as one cannot achieve a
$(1-\epsilon)\ln n$-approximation unless P = NP [WS11, DS14], nor an
$(f-\epsilon)$-approximation assuming the unique games conjecture [KR08].

There has been a recent growing endeavor to understand the set cover problem
in the dynamic setting. In the dynamic set cover problem, we are given as
input a dynamic universe $\mathcal{U}$ of at most $n$ elements and a fixed
collection $\mathcal{S}$ of $m$ sets, and the goal is to maintain a set cover
$\mathcal{S}_{\mathsf{alg}}\subseteq\mathcal{S}$ of small total cost, ideally
matching the best approximation for the static setting, within a low update
time. Given the aforementioned hardness results, one can hope for an
approximation factor that approaches either $\ln n$ or $f$, while achieving an
update time that approaches $O(f)$, which is the time required to specify an
update explicitly. Next, we survey the known results, distinguishing between
the _low-frequency regime_ ($f=O(\log n)$) and the _high-frequency regime_
($f=\Omega(\log n)$).

##### Low-Frequency Regime.

The vast majority of work on dynamic set cover has been devoted to the low-
frequency regime, based on the primal-dual approach. An
$O(f^{2})$-approximation with $O(f\log(m+n))$ amortized update time was given
in [BHI15], and an $O(f^{3})$-approximation with $O(f^{2})$ amortized update
time was given in [GKKP17]. A near-optimal approximation of $(1+\epsilon)f$
for the unweighted setting ($C\equiv 1$) was achieved for the first time in
[AAG+19], with (expected) amortized update time $O(f^{2}\log n/\epsilon)$,
which was improved to (expected) amortized update time $O(f^{2})$ (without any
$\epsilon$-dependency). The randomized algorithms of [AAG+19, AS21] were
strengthened to the general weighted setting via deterministic algorithms with
similar update time, still for the near-optimal approximation of
$(1+\epsilon)f$ [BHN19, BHNW21]. Very recently, this line of work on primal-
dual algorithms with amortized time bounds culminated in a
$((1+\epsilon)f)$-approximation algorithm that achieves a near-optimal
amortized update time of $O\left(\frac{f}{\epsilon^{3}}\log^{*}f+\frac{f\log
C}{\epsilon^{3}}\right)$ [BSZ23].

The algorithm of [BHN19] yields an amortized update time of
$O(\frac{f\cdot\log(Cn)}{\epsilon^{2}})$, and it is an _inherently global_
algorithm, in the sense that (1) it allows the underlying invariants to be
violated to some extent _in a global way_ (i.e., in some average sense), and
(2) it applies “global clean-up” procedures to restore the invariants.
Importantly, the global nature of that algorithm is what makes it amenable to
efficient _deamortization_ , as done in [BHNW21] to obtain a deterministic
$((1+\epsilon)f)$-approximation algorithm with
$O(\frac{f\log^{2}(Cn)}{\epsilon^{3}})$ _worst-case_ update time; note that
the deamortization of [BHNW21] loses a factor of $\frac{\log(Cn)}{\epsilon}$
in the update time. (See Table 1 for a summary of the results.)

##### High-Frequency Regime.

In contrast to the low-frequency regime, only two algorithms that dynamize the
classic _greedy_ algorithm are known, achieving $O(\log n)$\- and
$((1+\epsilon)\ln n)$-approximation with amortized update times $O(f\log n)$
and $O(\frac{f\log n}{\epsilon^{5}})$, respectively [GKKP17, SU23].

It seems inherently harder to dynamize the greedy algorithm (in the high-
frequency regime), as compared to the primal-dual algorithm (in the low-
frequency regime). We will try to substantiate this claim in the technical
overview of Section 2; however, the large gaps between the state-of-the-art
results in the two regimes may already provide partial evidence. For amortized
bounds, the algorithm of [BSZ23] in the low-frequency regime incurs only a
tiny extra $\log^{*}f\leq\log^{*}n$ factor in the update time over the ideal
$O(f)$ time bound (ignoring the dependencies on $\epsilon$ and $C$), whereas
the algorithms of [GP13, SU23] incur an extra $\log n$ factor. For worst-case
bounds, the algorithm of [BHNW21] in the low-frequency regime provides a low
worst-case update time, whereas the question of whether one can get
approximation $O(\log n)$ (or even worse) with low _worst-case_ update time
has remained open; only the naive $O(f\cdot n)$ time bound is known, even for
unweighted instances. Technically speaking, the algorithms of [GKKP17, SU23]
in the high-frequency regime apply “local clean-up” procedures whenever any
invariant is violated, which is problematic to deamortize; alas, in contrast
to the low-frequency regime, designing a dynamic greedy algorithm of global
nature seems highly challenging, as discussed in detail in Section 2.

##### Focus.

This work focuses on the dynamic set cover problem with worst-case update
time, primarily in the high-frequency regime — where no nontrivial worst-case
time bound is known. One may consider the gaps in our understanding of the
dynamic set cover problem with worst-case time bounds from two different
perspectives:

  1. 1.

In the high-frequency regime, the gap between the state-of-the-art amortized
($O(\frac{f\log n}{\epsilon^{5}})$ [SU23]) and worst-case (the naive $O(f\cdot
n)$) time bounds.

  2. 2.

For the state-of-the-art worst-case time bounds, the gap between the low-
frequency ($O(\frac{f\log^{2}(Cn)}{\epsilon^{3}})$ [BHNW21]) and the high-
frequency (the naive $O(f\cdot n)$) regimes.

The following fundamental question naturally arises:

######  Question 1.

Can one achieve an approximation of $O(\log n)$ (or even worse) for dynamic
set cover with any nontrivial _worst-case_ update time?

###  1.1 Our Contribution

This work provides the first dynamization of the greedy algorithm with a low
worst-case update time. To this end:

  1. 1.

We first overcome the aforementioned challenge by presenting the first
amortized greedy algorithm of global nature; see Section 2.2.1 for the
details.

  2. 2.

Second, we develop a lossless deamortization approach, i.e., the resulting
worst-case time-bound is just as good as the best amortized bound; see Section
2.2.2 for the details.

By employing our deamortization approach in conjunction with our new global
amortized algorithm, we obtain the following main result of this work (see
Table 1 for a summary of results).

######  Theorem 1.1 (High-frequency set cover).

For any set system $(\mathcal{U},\mathcal{S})$ that undergoes a sequence of
element insertions and deletions, where the frequency is always bounded by
$f$, and for any $\epsilon\in(0,\frac{1}{4})$, there is a dynamic algorithm
that maintains a $((1+\epsilon)\ln n)$-approximate minimum set cover in
$O\left(\frac{f\log n}{\epsilon^{2}}\right)$ deterministic worst-case update
time.

Not only does Theorem 1.1 resolve 1 in the affirmative, but it also achieves
_optimal_ bounds on both the approximation factor and the worst-case update
time, given the current state-of-the-art amortized result, excluding the
$\epsilon$ dependencies. Moreover, our worst-case update time actually
improves the $\epsilon$-dependence of the previous best amortized bound [SU23]
from $\epsilon^{-5}$ to $\epsilon^{-2}$. Therefore, we achieve an _optimal
deamortization_ of the previous best amortized algorithm in the high-frequency
regime. We stress that while the deamortization itself is optimal, the update
time bound of $O_{\epsilon}(f\log n)$ is not necessarily optimal; whether this
time bound can be improved (even for amortized bounds) remains an intriguing
open question.

To demonstrate the applicability of our deamortization approach, we employ it,
in conjunction with the aforementioned amortized algorithm of [BHN19] in the
low-frequency regime, to obtain the following result, which improves over the
worst-case time bound of $O(\frac{f\cdot\log^{2}(Cn)}{\epsilon^{3}})$
[BHNW21], first by shaving a factor of $\frac{\log(Cn)}{\epsilon}$, and then
by removing the dependency on the aspect ratio $C$.

######  Theorem 1.2 (Low-frequency set cover).

For any set system $(\mathcal{U},\mathcal{S})$ that undergoes a sequence of
element insertions and deletions, where the frequency is always bounded by
$f$, and for any $\epsilon\in(0,\frac{1}{4})$, there is a dynamic algorithm
that maintains a $((1+\epsilon)f)$-approximate minimum set cover in
$O\left(\frac{f\log n}{\epsilon^{2}}\right)$ deterministic worst-case update
time.

We note that our deamortization approach that proves Theorem 1.1 in the high-
frequency regime seamlessly extends to prove Theorem 1.2 in the low-frequency
regime. Consequently, we provide a unified algorithmic approach to the dynamic
set cover problem with worst-case time bounds. We emphasize that our approach
is naturally suitable specifically for the set cover problem. It would be
interesting to explore the possibilities of extending our approach beyond the
set cover problem; we leave this as an intriguing open question. Nonetheless,
the set cover problem is a fundamental covering problem, which encapsulates
several other important problems. As such, we believe that an approach
suitable for set cover is of rather general interest. In particular, our
approach leads directly to the following implications for the (minimum)
_dominating set_ and _vertex cover_ problems.

In the minimum dominating set problem, we are given a graph $G=(V,E)$, where
$n=|V|$, and each vertex has a cost assigned to it. The goal is to find a
subset of vertices $D\subseteq V$ of minimum total cost, such that for any
vertex $v\in V$, either $v\in D$ or $v$ has a neighbor in $D$. In the dynamic
setting, the adversary inserts/deletes an edge upon each update step. We
derive the result for the dominating set problem via a simple reduction to the
set cover problem (described in Section 6), which allows us to use our set
cover algorithm provided by Theorem 1.1 as a black box.

######  Theorem 1.3 (Dominating set).

For any graph $G=(V,E)$ that undergoes a sequence of edge insertions and
deletions, where the degree is always bounded by $\Delta$, and for any
$\epsilon\in(0,\frac{1}{4})$, there is a dynamic algorithm that maintains a
$((1+\epsilon)\ln\Delta)$-approximate minimum weighted dominating set in
$O\left(\frac{\Delta\log n}{\epsilon^{2}}\right)$ deterministic worst-case
update time.

We note that Theorem 1.3 provides the first non-trivial worst-case update time
algorithm for the (unweighted or weighted) minimum dominating set problem
222One could have used our simple reduction from dynamic dominating set to
dynamic set cover, in conjunction with the worst-case primal-dual set cover
algorithm in [BHNW21] as a black-box, to obtain a $(1+\epsilon)\cdot\Delta$
approximation with a worst-case update time of
$O(\frac{\Delta\cdot\log^{2}(Cn)}{\epsilon^{3}})$. Such a result has not been
reported in the literature, but more importantly, its approximation ratio
$\approx\Delta$ is far worse than the approximation ratio $\approx\ln\Delta$
that we aim for. as with our set cover results, there is no dependence
whatsoever on the costs. Our worst-case time bound matches the previous best
amortized bound for the problem [SU23], and it also improves its
$\epsilon$-dependence from $\epsilon^{-5}$ to $\epsilon^{-2}$.

Next, for the minimum (weighted) vertex cover problem, by setting $f=2$ in
Theorem 1.2, we directly get an improvement of the state-of-the-art worst-case
update time bound for $(2+\epsilon)$-approximate vertex cover: from
$O(\frac{\log^{2}(Cn)}{\epsilon^{3}})$ [BHNW21] to $O\left(\frac{\log
n}{\epsilon^{2}}\right)$.

reference | approximation | update time | worst-case? | weighted?
---|---|---|---|---
[GKKP17] | $O(\log n)$ | $O(f\log n)$ | no | yes
[SU23] | $(1+\epsilon)\ln n$ | $O\left(\frac{f\log n}{\epsilon^{5}}\right)$ | no | yes
new | $(1+\epsilon)\ln n$ | $O\left(\frac{f\log n}{\epsilon^{2}}\right)$ | yes | yes
[BHI15] | $O(f^{2})$ | $O(f\log(m+n))$ | no | yes
[GKKP17, BCH17] | $O(f^{3})$ | $O(f^{2})$ | no | yes
[AAG+19] | $(1+\epsilon)f$ | $O\left(\frac{f^{2}}{\epsilon^{5}}\log n\right)$ | no | no
[BHN19] | $(1+\epsilon)f$ | $O\left(\frac{f}{\epsilon^{2}}\log(Cn)\right)$ | no | yes
[BHNW21] | $(1+\epsilon)f$ | $O\left(\frac{f^{2}}{\epsilon^{3}}+\frac{f}{\epsilon^{2}}\log C\right)$ | no | yes
[BHNW21] | $(1+\epsilon)f$ | $O\left(\frac{f\log^{2}(Cn)}{\epsilon^{3}}\right)$ | yes | yes
[AS21] | $f$ | $O\left(f^{2}\right)$ | no | no
[BSZ23] | $(1+\epsilon)f$ | $O\left(\frac{f}{\epsilon^{3}}\log^{*}f+\frac{f\log C}{\epsilon^{3}}\right)$ | no | yes
new | $(1+\epsilon)f$ | $O\left(\frac{f\log n}{\epsilon^{2}}\right)$ | yes | yes
Table 1: Summary of results on dynamic set cover.

##  2 Technical Overview

In this section we give a technical overview of our contribution. In Section
2.1 we set up the ground by surveying the known techniques and approaches. In
Section 2.2 we discuss the main technical challenges left open by previous
work, and then turn to presenting the key technical novelty behind our work
and demonstrating how it overcomes the main challenges. Along the way, we try
to convey some conceptual highlights of this work. We refer to Sections 3, 4
and 5 for the full, formal details.

###  2.1 The Known Amortized Algorithms

##### Hierarchical Data Structure.

Every set $s\in\mathcal{S}$ is assigned a level value in the range
$[-1,O(\log(Cn))]$, where $-1$ is reserved for sets not in the cover. Every
element $e\in\mathcal{U}$ is assigned to a unique set $\mathsf{asn}(e)$ in the
dynamic set cover solution, where $e$ shares the same level
$\mathsf{lev}(e)=\mathsf{lev}(\mathsf{asn}(e))$ as the set to which it is
assigned; inversely, we have the cov(ering) set
$\mathsf{cov}(s)=\\{e\mid\mathsf{asn}(e)=s\\}$ of $s$, which consists of all
elements assigned to set $s$.

####  2.1.1 The Fully Local Approach

In the original approach from [GKKP17], their algorithm maintains the
following invariant.

######  Invariant 2.1 ($O(\log n)$-approximation, [GKKP17]).

The following two conditions regarding the hierarchical structure hold at any
time (i.e., before any update step).

  1. (1)

For any set $s$ in the current solution, it holds that
$|\mathsf{cov}(s)|/\mathsf{cost}(s)\in[2^{\mathsf{lev}(s)},2^{\mathsf{lev}(s)+10}]$.333In
[GKKP17] the levels are negative and they consider the ratio
$\frac{\mathsf{cost}(s)}{|\mathsf{cov}(s)|}$. In this paper we will consider
the inverse ratio $\frac{|\mathsf{cov}(s)|}{\mathsf{cost}(s)}$ and so the
levels will be positive. The two are completely equivalent.

  2. (2)

For any set $s$ and level $k$, $\\{e\mid e\in s,\mathsf{lev}(e)=k\\}$ has size
at most $2^{k+10}\cdot\mathsf{cost}(s)$.

[GKKP17] used what we shall refer to as a _fully local_ approach to maintain
both conditions of 2.1 at any time; namely, whenever 2.1(1) or 2.1(2) is
violated, even for a single set $s$, the algorithm performs a local change,
which aims at restoring the condition for set $s$. At the core of such a local
change — which we shall refer to as a local fall or local rise of $s$
(depending on whether the level of $s$ increases or decreases) — is a change
to the level of $s$, which is accompanied with changes to levels of elements
that join or leave $\mathsf{cov}(s)$. Of course, a local fall/rise of a single
set may trigger further violations of the conditions, which are handled by
performing further local falls and rises. The resulting cascade of local falls
and rises is repeated until the conditions hold.

####  2.1.2 The Partially Global Approach: From $O(\log n)$ to
$(1+\epsilon)\ln n$ Approximation

As observed in [SU23], 2.1 has some inherent barriers against achieving a
$(1+\epsilon)\ln n$ approximation. Therefore, in [SU23], a different set of
conditions were proposed in order to optimize the constant factor preceding
$\ln n$ to $1+\epsilon$, as given in the following invariant. We remark that
this invariant was not maintained by [SU23]; only a relaxation of the
invariant was maintained, as discussed below.

######  Invariant 2.2 ($(1+\epsilon)\ln n$-approximation, [SU23]).

Set $\beta=1+\epsilon$. The following two conditions regarding the
hierarchical structure hold at any time.

  1. (1)

For any set $s$ in the current solution, it holds that
$|\mathsf{cov}(s)|/\mathsf{cost}(s)\geq\beta^{\mathsf{lev}(s)-1}$.

  2. (2)

For any set $s$ and level $k$, $N_{k}(s)=\\{e\mid e\in s,\mathsf{lev}(e)\leq
k\\}$ has size less than $\beta^{k+2}\cdot\mathsf{cost}(s)$.

There are several differences between 2.2 and 2.1, which are crucial for
improving the approximation from $O(\log n)$ to $(1+\epsilon)\ln n$. One
difference is the usage of $\beta=1+\epsilon$ rather than $2$. Another
difference lies in the second condition: While in 2.1 it bounds the number of
elements in a set $s$ at level exactly $k$, 2.2 provides a stronger bound on
the total number of elements belonging to $s$ at all levels $\leq k$.444In
[SU23], $N_{k}(s)$ is defined as $N_{k}(s)=\\{e\mid e\in
s,\mathsf{lev}(e)<k\\}$ and the upper bound on $|N_{k}(s)|$ is
$\beta^{k+2}\cdot\mathsf{cost}(s)$; this is of course an equivalent
formulation (where $k$ is replaced by $k+1$). Clearly, 2.2 is stronger than
2.1, and it turns out to be problematic to maintain efficiently.

The key behind the improvement of [SU23] to the approximation factor, while
achieving the same amortized update time, is to abandon the fully local
approach of [GKKP17], which performs a cascade of local falls and rises until
both conditions of the invariant are maintained, following any update step.
Instead, the approach taken by [SU23], which we shall refer to as _partially
global_ , is to maintain only the second condition of the invariant for any
set; that is, whenever there is any violation of 2.2(2), the algorithm
perofrms a local rise. On the other hand, the first condition is only
maintained in a _global_ manner in [SU23]; more specifically, the algorithm
waits until 2.2(1) is widely violated in many places in the hierarchical
structure, and then performs a _reset_ procedure on a carefully chosen part of
the hierarchical structure — which amounts to running the standard greedy
algorithm on that part — to restore 2.2(1); roughly speaking, 2.2(1) only
holds in an average sense (or for an average set), and does not necessarily
hold for any set $s$. The authors of [SU23] prove that the approximation
factor is $(1+\epsilon)\ln n$ even by assuming that 2.2(1) only holds in an
average sense, in a proof that follows closely the standard proof of
$\ln(n)$-approximation for the classic static greedy algorithm.

Summarizing:

  * •

The fully local algorithm of [GKKP17] locally maintains both conditions of the
invariant, by persistently performing local falls and rises to sets that
violate the conditions.

  * •

In the partially global algorithm of [SU23], only the second condition is
locally maintained, by performing local rises to sets that violate it. On the
other hand, the first condition is maintained _globally_ , which in particular
means that no local falls occur.

  * •

In both previous algorithms [GKKP17, SU23], the proofs of the approximation
factor follow rather closely known analyses of the classic greedy algorithm.

###  2.2 Our Approach

####  2.2.1 A Fully Global Amortized Algorithm

We remind that our goal is to obtain the _first_ greedy-based set cover
algorithm with a low _worst-case_ update time. The naive algorithm would
recompute from scratch the greedy algorithm on the entire system following
each update step, but this yields an update time of $O(f\cdot n)$. To achieve
a low worst-case update time, the first suggestion that comes to mind is to
try and deamortize one of the aforementioned amortized algorithms [GKKP17,
SU23]. As mentioned, the algorithms [GKKP17] of [SU23] are fully local and
partially global, respectively; in particular, both algorithms perform local
rises, for any set that violates the second condition of the corresponding
invariant. The running time of a local rise of any set $s$ to level $j$ is at
least linear in the number of elements that join $\mathsf{cov}(s)$, which is
by design around $\beta^{j}$. Thus, de-amortizing the algorithms of [GKKP17,
SU23] with a low worst-case update time implies that one cannot complete even
a single high-level local rise. Of course, one can perform the required local
rises with a sufficient amount of delay, by maintaining a queue of all sets
that violate the second invariant and handling them one after another, however
delaying even a single local rise may blow up the approximation factor; e.g.,
consider an extreme (unweighted) case where each element is covered by a
singleton set at level 0, yet there is a single set $s$ that contains all $n$
elements, which needs to perform a local rise to level $\log n$, as a result
of which each element will have left its singleton covering set and joined
$\mathsf{cov}(s)$. We note that this extreme case, which incurs the worst-
possible approximation of $n$ (for unweighted instances), is “invalid”, in the
sense that it shouldn’t have been created in the first place, as $s$ should
have made a local rise to cover many elements well before all of them have
been inserted; however, one can embed this invalid instance inside larger
instances in obvious ways to create various instances of the same flavor that
incur very poor approximation.

A natural two-step strategy would therefore be to first obtain a _fully
global_ amortized algorithm, where we eliminate not just the local falls as in
[SU23], but also the local rises — so that both conditions of 2.2 will be
maintained only in a global average sense, and in particular they may be
violated locally by some sets; moreover, the conditions of 2.2 will be
restored only through a global reset procedure on a carefully chosen part of
the hierarchical structure. The second step would be to de-amortize the
resulting fully global algorithm, which seems much more natural and promising
than de-amortizing the fully local or partially global algorithms [GKKP17,
SU23]. Such a two-step strategy was employed before in a similar context:

  1. 1.

Bhattacharya et al. [BHN19] dynamized the primal-dual $f$-approximation
algorithm to achieve $((1+\epsilon)f)$-approximation with an amortized update
time of $O(\frac{f\cdot\log(Cn)}{\epsilon^{2}})$, via a fully global algorithm
— which, similarly to the above, may violate the conditions of the underlying
invariant locally by some sets, and only tries to satisfy them in a global
sense, and to restore them through a global reset procedure on a carefully
chosen part of the hierarchical structure. _As mentioned, the two known
dynamic greedy algorithms are not fully global._

  2. 2.

Bhattacharya et al. [BHNW21] deamortized the fully global amortized algorithm
of [BHN19], to obtain a worst-case update time of
$O(\frac{f\cdot\log^{2}(Cn)}{\epsilon^{3}})$. _The fully global amortized
algorithm satisfies some “nice” properties, which are amenable to
deamortization; it is unclear if similar properties can be achieved for an
amortized greedy algorithm. Moreover, the deamoritzation of[BHNW21] loses a
factor of $\frac{\log(Cn)}{\epsilon}$._

Two challenges arise:
_Challenge 1. Fully global amortized algorithm: Primal-dual is easier than
greedy._ The conditions in the invariant of the primal-dual algorithm of
[BHN19] are the complementary slackness conditions, which are easier to
maintain than the conditions in 2.2; in particular, the analog complementary
slackness condition to 2.2(2) (see Section 5) is to upper bound the weight
$\omega(s)$ of any set $s$ by its cost $\mathsf{cost}(s)$, where
$\omega(s)=\sum_{e\in S}\omega(e)$ and $\omega(e)$ is basically
$\beta^{-\mathsf{lev}(e)}$ ($\mathsf{lev}(e)$ is the dynamic level of $e$). On
the other hand, the condition in 2.2(2) applies not just to any set, but also
to every possible level $k$, which makes it inherently more difficult to
maintain.
_Challenge 2. A lossless deamoritzation._ As the greedy algorithm appears to
be inherently more difficult to dynamize and “globalize” than the primal-dual
algorithm, it is only natural to expect that the task of deamortizing an
amortized greedy algorithm would be harder than for a primal-dual algorithm.
Moreover, our goal is to attain a lossless deamortization, where the worst-
case update time does not exceed the amortized bound by a factor of
$\frac{\log(Cn)}{\epsilon}$, as in [BHNW21]. Next, we describe Challenge 1 in
more detail, and highlight the main insights that we employed in order to
overcome it. The discussion on Challenge 2 is deferred to Section 2.2.2.

As mentioned, in [SU23] the resets are executed on only part of the system. To
be more precise, they execute a reset up to some _critical_ level, which
amounts to running the standard static greedy algorithm only on sets and
elements that their level is up to the critical level. In a sense, it just
“reshuffles” the system up to that critical level, and this does not clean up
the whole system obviously, but the authors show that such a reset does clean
up enough for the approximation factor to hold, and that the system has
obtained enough “credits” for each set and element up to the critical level to
change levels in the reset. Thus, to obtain a _fully global_ amortized
algorithm, it seems necessary to use this idea of resets only up to certain
levels.

It turns out that “globalizing” 2.2(2) is inherently different and harder than
globalizing 2.2(1), which is perhaps the reason that the authors of [SU23]
settled for a partially global algorithm rather than a fully global one.
First, let us compare the effect to the approximation factor, of postponing
local falls versus that of postponing local rises; recall that local falls and
rises correspond to the first and second conditions of 2.2, respectively. To
simplify the discussion, consider the unweighted case. If there exists a set
$s$ that violates 2.2(1) (and needs to perform a local fall), even by a lot —
in the extreme case $|\mathsf{cov}(s)|=0$, then this will not have a direct
effect on other sets, and at worst we have caused the set cover size to grow
by one (by having $s$ in the set cover even though it may not need to be
there). Consequently, one can define a global violation to 2.2(1) for each
prefix of levels in the obvious way (whenever an $\epsilon$-fraction of the
sets up to level $k$ violate the condition, this prefix is “dirty”), and it is
not difficult to show that the approximation is in check as long as no prefix
of levels is dirty. In contrast, if there is a set $s$ that violates 2.2(2) as
$|N_{k}(s)|\geq\beta^{k+1}$, and its local rise to level $k$ is postponed,
this could affect many sets, since each element in $N_{k}(s)$ may be covered
by a different set, and also $s$ might not even be in the solution currently.
Moreover, a single local rise could create possibly many sets that violate
2.2(1), and they may all become empty following the rise. So one local rise
may create possibly many sets that violate 2.2(1), by a lot. Moreover, those
violated sets may lie in multiple levels, which makes it harder to quantify
the dirt across one level. If we again consider the extreme case, where
$|N_{k}(s)|=n$, then obviously the optimal set cover size is one, and by not
executing the rise our maintained solution can be arbitrarily larger, as
discussed in the beginning of Section 2.2.1. And indeed, the approximation
factor analysis of both [GKKP17] and [SU23] rely heavily on the fact that
2.1(2) and 2.2(2) (respectively) hold locally for each set. If we aim for a
globalization of this condition, we need to meet three objectives:

  1. 1.

We first need to define a _global_ notion of “dirt”, meaning a global measure
that determines how far off we are from the “ideal guarantee” — where each set
obeys locally both conditions of 2.2. This definition must take into account
local rises that are being postponed (in contrast to [SU23] — and this is the
hard part), and we want this global notion of dirt to be defined for any
level, and in particular for any _prefix_ of levels (all levels up to a
certain level — as in [SU23]), in order to determine a “critical level” to do
a reset up to. Meaning, we need to be able to determine whether “the system up
to some level $k$ is dirty” or not.

  2. 2.

Next, we need to come up with a “global algorithm”, which would correspond to
the global notion of dirt, and in particular would maintain a relevant global
invariant by cleaning up the dirt _globally_ via _resets_ up to a certain
critical level.

  3. 3.

Lastly, an _inherently_ different approximation factor analysis seems to be
necessary, since the known ones crucially rely on the validity of the second
condition of the invariants (2.1 or 2.2) for every set; we need a new argument
that would correspond to the new global invariant, which is defined by the new
notion of global dirt.

##### Naive Attempt.

The first attempt for meeting the first objective is to use a binary
distinction between active and passive elements.555This terminology of active
and passive elements is from [BHNW21]. We believe it is instructive to use the
same terminology, even though our definitions of active/passive are not the
same as [BHNW21], since we aim at achieving a unified deamorization approach,
applicable also to the low-frequency regime. We will say that each element
upon insertion is passive, and once it participates in a reset it becomes
active. We shall consider each passive element at level $k^{\prime}$ as a
“dirt unit” at level $k^{\prime}$. Once the number of dirt units _up to_ level
$k$ surpasses an $\epsilon$-fraction of the total number of elements up to
level $k$, we say that the system is $k$-dirty.

For the second objective, we will maintain the invariant that the system is
never $k$-dirty for any $k$. To do so, we will execute a reset (static greedy
algorithm) on the subsystem of elements and sets that lie up to level $k$
immediately when the system becomes $k$-dirty. Following this reset, by
definition of our global dirt, all elements up to $k$ become active, which
cleans up all dirt up to level $k$, and the invariant holds. Since passive
elements are newly inserted elements that have not yet participated in a
reset, if each inserted element arrives with $\frac{1}{\epsilon}$ credits,
then we would have one credit for each element participating in a reset.

The problem with this naive suggestion lies within the third objective,
meaning the approximation factor may blow up. Immediately following a reset up
to level $k$ indeed an element $e$ participating in this reset does not want
to be part of a rise to any level up to $k$ (because the greedy algorithm
would have taken care of that), but since these resets are executed on only
part of the system, it could be that $e$ still wants to rise to some level
higher than $k$. Meaning, if an element $e$ wanted to rise to some level
$k^{\prime}>k$ before the reset to level $k$, a reset to level $k$ does not
change this, since it only “shuffles” elements at level up to $k$, so in a
sense this element has not been fully “cleaned” yet. The same elements that
wanted to rise to level $k^{\prime}$ still want to rise to there after the
reset to level $k$. Thus, even if all elements are active, which would mean
that our system is entirely “clean”, it could be that many rises need to
occur, which may blow up the approximation factor. Therefore, this binary
definition of active or passive is insufficient, and we need to revise our
definition of global dirt — taking this issue into account.

##### Meeting Objective $1$ (Global Dirt).

It seems that our initial binary definition of active/passive must be “level-
sensitive” for it to work. Meaning, an element will be considered active _up
to a certain level_ , and then passive _from that level upwards_. Let us
define the _passive level_ of an element $e$ to be this certain level, denoted
by $\mathsf{plev}(e)$, and roughly speaking it will be one level higher than
the reset level of the highest reset in which $e$ participated in since it was
inserted. An element $e$ will be “clean” below its passive level, and “dirty”
at or above it, and it is important to have
$\mathsf{lev}(e)\leq\mathsf{plev}(e)$ (see the discussion below). Denote by
$A_{k}$ (respectively, $P_{k}$) the set of all elements $e$ with
$\mathsf{lev}(e)\leq k$ and $\mathsf{plev}(e)$ larger than (resp., no larger
than) $k$. An element in $A_{k}$ (resp., $P_{k}$) will be called $k$-active
(resp., $k$-passive). We define the system to be $k$-dirty if
$|P_{k}|>2\epsilon\cdot|A_{k}|$. Since $A_{k}\cup P_{k}$ is the set of all
elements at level at most $k$, the system is $k$-dirty if roughly more than a
$2\epsilon$-fraction of all elements at level up to $k$ have a passive level
also up to $k$.

##### Meeting Objective $2$ (Global Algorithm).

We want to maintain the following invariant:

######  Invariant 2.3 (see 3.1 for more details).

The following three conditions should hold:

  1. (1)

For any set $s$ in the current solution, we have
$\frac{|\mathsf{cov}(s)|}{\mathsf{cost}(s)}\geq\beta^{\mathsf{lev}(s)}$.

  2. (2)

Define $N_{k}(s)=A_{k}\cap s$. For any set $s\in\mathcal{S}$ and level $k$, we
have $\frac{|N_{k}(s)|}{\mathsf{cost}(s)}<\beta^{k+1}$.

  3. (3)

For any level $k$, we have $|P_{k}|\leq 2\epsilon\cdot|A_{k}|$.

The first two conditions of the invariant correspond to the two in 2.2,
respectively. It may seem as though the first and second conditions imply
local constraints, since they hold for each set $s$. However, we make two
crucial changes in the definitions: In the first condition, $\mathsf{cov}(s)$
is redefined to include also deleted elements that have not gone through a
reset, and in the second condition, $N_{k}(s)$ is redefined to consider only
_$k$ -active_ elements. In a sense, these two conditions only consider “clean”
elements. Lastly, we need to ensure that the vast majority of elements are
indeed “clean”. Meaning, we want to prevent the accumulation of too many
$k$-passive elements, for each $k$, otherwise the first two conditions would
be meaningless, since a large fraction of elements in the system would not be
considered, which may blow up the approximation factor. To summarize, the
first two conditions are local constraints that disregard all “passive”
elements (for each level), and the third condition ensures that such passive
elements (for each level) are scarce, and this is where the global relaxation
for the first two comes into play. Intuitively, the purpose of the third
condition is to _divert_ dirt from the first two “local” conditions (which are
analogous to 2.2) to the third, which is _global_ by design and thus crucial
to achieve a fully global algorithm.

To maintain this invariant we will execute a _reset_ up to level $k$ once
$|P_{k}|>2\epsilon\cdot|A_{k}|$, which amounts to running the static greedy
algorithm on the subsystem of elements and sets that are up to level $k$, and
removing deleted elements up to level $k$ from the system. We want to trigger
resets only once there is a violation to the third condition. Thus, when an
element is inserted, we will assign its passive level to be its actual level;
in a sense, it can be considered as “completely passive”, since it cannot be
in any set $A_{k}$ and $N_{k}(s)$ for any $k$ and $s$. When an element is
deleted, we will not remove it from the system yet, and instead just mark it
as _dead_ , and assign its passive level to be its actual level. Therefore,
deletions cannot reduce the size of $\mathsf{cov}(s)$ for any $s$. Thus,
insertions and deletions cannot cause violations to the first two conditions,
and instead they add “passiveness” to the system, which will eventually
trigger a violation to the third condition.

We want a reset up to level $k$ to completely “clean up” everything up to $k$.
Meaning, we would want $P_{k^{\prime}}=\emptyset$ for any $k^{\prime}\leq k$
following the reset. Thus, by definition of $P_{k}$, each participating
element must have a passive level higher than $k$ following the reset. Not
only do we want a reset to level $k$ to clean up everything up to that level,
we also require that it would not create more dirt (or “passiveness”) in any
higher level, otherwise a reset can trigger another (higher) reset, which
could blow up the update time. We want only insertions and deletions to create
dirt. Thus, if for example a reset to level $k$ is being executed and as a
result a participating set $s$ wants to be created at level $k+5$, because it
contains about $\mathsf{cost}(s)\cdot\beta^{k+5}$ participating elements, we
will not allow this, since this affects all levels between $k$ and $k+5$.
Therefore, we will _truncate_ any reset to level $k$ at level $k+1$, meaning
we will not allow participating sets to cover at any level higher than $k+1$.
This way levels higher than $k$ are not affected by the reset, meaning there
is no change to $P_{k^{\prime}}$ and $A_{k^{\prime}}$ for any $k^{\prime}>k$,
and notice that all participating elements in a reset up to level $k$ will end
up at a level up to $k+1$ following the reset. We conclude that following a
reset to level $k$ the first two conditions still hold by design of the greedy
algorithm and the level assignment in it, the third condition holds since
$|P_{k^{\prime}}|=0$ for any $k^{\prime}\leq k$, and the reset has not raised
$|P_{k^{\prime}}|$ or lowered $|A_{k^{\prime}}|$ for any $k^{\prime}>k$, so
this reset cannot trigger a reset at any higher level. For more details
regarding the algorithm description, see Section 3.2.

Since each participating element must have a passive level higher than $k$
following a reset to level $k$, each participating element will be assigned a
passive level of the maximum between $k+1$ and its previous passive level. In
this way, notice that the passive level of an element will never be lower than
its level, and that the passive level of any element throughout the entire
update sequence is monotonically non-decreasing. This means that the number of
different passive levels an element can go through during the update sequence
is bounded by the number of levels in the system, and it turns out that this
bound is what mandates the amortized update time to be $O(f\cdot\log n)$,
neglecting dependencies on $\epsilon$ and $C$. To show this, consider a token
scheme which gives each inserted element $O(f)$ tokens for each passive level
it could be at. The key observation is that even if there are multiple resets
to the same level $k$ throughout the update sequence, each element can only
once be part of the collection $P_{k}$ that triggers the reset to level $k$
once $|P_{k}|>2\epsilon\cdot|A_{k}|$, as afterwards its passive level would be
at least $k+1$, and it will never decrease. Thus, we can give each element
tokens to be responsible for only one reset for each level throughout the
entire sequence. Since a reset to level $k$ occurs once $|P_{k}|$ is (roughly)
a $2\epsilon$-fraction of all elements up to level $k$, handing out
$O(\frac{f}{\epsilon})$ tokens for each element per level would be enough to
redistribute the tokens such that each participating element has $O(f)$
tokens, enough to enumerate the sets containing it and update the
corresponding data structures regarding the new level. We have thus obtained
an algorithm with $O(f\cdot\log n)$ amortized update time 666The exact
amortized update time is $O(\frac{f\cdot\log(Cn)}{\epsilon^{2}})$, since there
are roughly $\frac{\log(Cn)}{\epsilon}$ levels. In Section 2.2.2 we explain
how to get rid of the $C$ factor., which maintains 2.3 that is based on our
definition of global dirt. The final objective is to show that we achieve the
desired approximation factor.

##### Meeting Objective $3$ (Approximation Factor).

We present a highly nontrivial proof for the approximation factor of
$(1+\epsilon)\cdot\ln n$, which might be of independent interest. Our proof
relies on 2.3, which uses a global notion of dirt, and as such it has to
circumvent several technical hurdles that the previous proofs [GKKP17, SU23]
did not cope with. See Lemma 3.1 and Corollary 3.1 for the details. See Figure
1 for an illustration of the definitions and procedures given in the last few
paragraphs.

Figure 1:  On the left: Each black circle represents a single element with
level and passive level up to $4$, and is assigned to different collections
$A_{k}$ and $P_{k}$. Recall that for each element $e$,
$\mathsf{plev}(e)\geq\mathsf{lev}(e)$. We can see the following properties: If
an element is in $P_{k}$ it is also in $P_{k^{\prime}}$ for any
$k^{\prime}>k$. If an element is in $A_{k}$ it is also in $A_{k^{\prime}}$ for
any $k^{\prime}<k$ if its level is up to $k^{\prime}$. For each $k$ we have
that $A_{k}\cup P_{k}$ is the collection of all elements up to level $k$, and
for each $k$ $A_{k}\cap P_{k}=\emptyset$. On the right: Following a reset up
to level $3$, we have that $P_{i}=\emptyset$ for any $i\leq 3$, and the level
of all elements that were at level up to $3$ are now at a level up to $4$, but
the passive level of each such element is now at least $4$. The black circles
here can represent several elements. Notice that ten elements participated in
this reset, and these elements are represented by one of the five black
circles. Any element that was in $P_{4}$ before the reset is still there
after.

####  2.2.2 A Lossless Deamortization

Recall that an efficient deamortization approach was given in the low-
frequency regime, where [BHNW21] deamortized the fully global amortized
primal-dual algorithm of [BHN19]. However, the worst-case update time exceeds
the amortized bound by a factor of $\frac{\log(Cn)}{\epsilon}$.

The focus of this work is the high-frequency regime, which, as mentioned
already, appears to be more challenging when it comes to the dynamic setting.
Having obtained a fully global algorithm with amortized update time that
matches the previous best amortized bounds [GKKP17, SU23], our next challenge
is to deamortize it to achieve a good worst-case update time. We develop a
lossless deamortization approach for the high-frequency regime, using which we
achieve a worst-case update time that matches the best amortized bounds, and
actually shaves off a $\epsilon^{-3}$ factor from [SU23]. We then apply our
deamortization approach also in the low-frequency regime, first to shave off a
$\log(Cn)$ factor, and then to remove the dependency on the aspect ratio $C$.

Our deamortization approach is reminiscent of the one in the low-frequency
regime [BHNW21], since we need to cope with similar technical difficulties.
Nonetheless, our approach has to deviate from the previous one in several key
points. We next discuss some of those technical difficulties, highlighting the
new hurdles that we overcame on the way to achieving a lossless deamorization.

Consider a reset to level $k$. If $k$ is large enough, then the reset cannot
be carried out within a single update step, but rather needs to be simulated
on _the background_ within a long enough time interval, where in each update
step we can execute a small amount of computational steps. We shall denote by
$\mathsf{reset}(k)$ a reset instance to level $k$; roughly speaking, we would
like to execute $O(f/\epsilon)$ computational steps of $\mathsf{reset}(k)$ for
any possible level $k$ following each update step, so that the worst-case
update time will be the number $O(\log_{\beta}(Cn))$ of levels times
$O(f/\epsilon)$, namely $O(\frac{f\log(Cn)}{\epsilon^{2}})$. Importantly,
before a $\mathsf{reset}(k)$ instance can start, we first need to copy the
contents of the current _foreground_ (output) solution up to level $k$, as
well as the underlying data structures, to a chunk of local memory on the
background, which is disjoint from the solution and data structures on the
foreground as well as from those of any other reset instance that is running
on the background. It is crucial that the contents of memory in any
$\mathsf{reset}(k)$ instance will form an independent copy of the foreground
solution and data structures up to level $k$. Only after we have copied those
contents, we turn to simulating the execution of the reset on the background.
Finally, after termination of the reset in the background, we need to bring
back the new solution and data structures up to level $k$ that we have in the
background to the foreground (and overwrite it); a central crux (discussed
below) is that this last part needs to be carried out within a single update
step.

If only one reset were to run in the background at any point in time, things
would be easy. However, multiple resets at different levels need to run
together, and they all need to be simulated on the background at the same
time; this issue, alas, may lead to various types of conflicts and
inconsistencies. Indeed, as mentioned, when a reset to level $k$ starts, we
first copy the contents of the foreground solution and data structures up to
level $k$ to the background. However, these contents in the foreground may be
partially or fully overwritten by resets that get terminated before the one
that has just started, since any terminating reset is supposed to bring back
(and overwrite) its background solution and data structures to the foreground.
This creates inconsistencies between the views of the foreground by different
reset instances.

The key question is: How should we resolve such inconsistencies? It is natural
to give a higher precedence to a reset instance at a higher level than to a
lower level instance, as it essentially operates on a super set-system (a
superset of sets and elements), however the time needed to complete a reset
grows with the reset level, hence a reset at a lower level might have started
the reset well after the higher level reset, so it should hold a more up-to-
date foreground view.

We will not discuss the answer to this question in detail here; the formal
answer appears in Section 3. Instead, we wish to highlight a key difference
between our approach and that of [BHNW21], which allows us to shave the extra
$\log_{\beta}(Cn)$ factor in the time bound.

Both our algorithm and that of [BHNW21] assign elements and sets to levels at
most $O(\log_{\beta}(Cn))$, and for each level $k$ there is a
$\mathsf{reset}(k)$ instance that is running on a separate chunk of local
memory on the background. The executions of $\mathsf{reset}(k)$ in the two
algorithms are quite different. First, while [BHNW21] simulates the water-
filling primal-dual algorithm, we need to simulate the greedy algorithm. There
are also other differences, including the exact way that the algorithms cope
with adversarial element updates that occur during the resets’ simulations.
The key difference, however, is in the manner in which we resolve the
aforementioned inconsistencies, briefly described next.

In both algorithms, when $\mathsf{reset}(k)$ terminates, it switches its local
memory to the foreground and aborts all other lower level instances
$\mathsf{reset}(i)$, for all $i<k$. To ensure that all the aborted instances
$\mathsf{reset}(i)$ will have an independent local copy of the current data
structures up to level $i$, the approach of [BHNW21] is that, besides
executing the water-filling procedures, the instance $\mathsf{reset}(k)$ will
also be responsible for initializing an independent copy of the data
structures up to level $i$ for instance $\mathsf{reset}(i)$, for all $i<k$,
right after $\mathsf{reset}(i)$ is aborted by $\mathsf{reset}(k)$. This is the
main reason that the algorithm of [BHNW21] has a quadratic dependency on
$\log_{\beta}(Cn)$, as $\mathsf{reset}(k)$ needs to prepare the initial memory
contents for all other instances below it after it terminates, and it is
crucial to carry this out within a single update step, again to avoid
inconsistencies.

In our approach, to save the extra $\log_{\beta}(Cn)$ factor in the update
time, the $\mathsf{reset}(k)$ instance will no longer be responsible for
initializing the memory contents of $\mathsf{reset}(i)$, for all $i<k$, right
after $\mathsf{reset}(i)$ is aborted by $\mathsf{reset}(k)$. Instead, each
instance $\mathsf{reset}(i)$ will initialize its own memory in the background
by copying data structures in the foreground up to level $i$, and only when
the initialization phase is done, the actual simulation procedure begins (of
either the greedy algorithm in our case, or the water-filling algorithm as in
[BHNW21]). Moreover, we would like to carry out the termination of any
$\mathsf{reset}(k)$ instance in a single update step, meaning within
$O(\log_{\beta}(Cn))$ time. Alas, the caveat of such a modification is that we
are no longer able to determine in constant time the levels of sets and
elements on the foreground (although we are able to do so in each
$\mathsf{reset}(k)$ instance running on the background). Instead, we propose
an _authentication_ process for determining the foreground level of any set or
element in $O(\log_{\beta}(Cn))$ time. We demonstrate that despite this
caveat, we are able to achieve the desired update time of
$O\left(\frac{f\log(Cn)}{\epsilon^{2}}\right)$, see Section 3.3 for details.

##### Removing Dependency on Aspect Ratio.

The approach suggested above can only achieve a worst-case update time of
$O_{\epsilon}(f\log(Cn))$, which could be prohibitively slow for a
sufficiently large aspect ratio $C$. To remove the dependence on the aspect
ratio, the first natural approach is to apply our algorithm only on the lowest
window of $10\log_{\beta}n$ consecutive levels, which starts with the lowest
non-empty level (i.e., which contains at least one element), and directly add
all sets to our set cover solution on all higher levels (after the window).
The intuition behind this approach is that sets belonging to levels higher
than the lowest window have negligible costs compared to sets inside the
lowest window, so adding those sets to our set cover solution does not change
our approximation ratio significantly.

The main issue with this approach is that the lowest non-empty level, and thus
the lowest window, changes dynamically. In particular, the adversary could
delete elements in the lowest window. Once this window becomes empty, the
algorithm must switch its attention to a different window at higher levels.
Alas, since the algorithm did not maintain any structure on higher levels, and
in particular the underlying invariants could be completely violated outside
the lowest window, restoring the necessary structures and invariants on high
levels due to a sudden switch would be a heavy computational task, which
cannot fit in our worst-case time constraints. If instead of considering the
lowest window of $10\log_{\beta}n$ consecutive levels, we consider a window
that consists of the lowest $10\log_{\beta}n$ non-empty levels, we will still
run into the same problem — the adversary could make all those non-empty
levels empty (and thus to trigger a switch to a higher window) much earlier
than the algorithm may hope to restore the invariants at higher levels, since
it is possible that the lower non-empty levels occupy far less elements than
the higher ones.

To fix this issue, let us partition the entire level hierarchy into a sequence
of fixed non-overlapping windows, each consisting of $c\log_{\beta}n$
consecutive levels for a constant $c$; for concreteness, we assume in this
discussion that $c=10$. Instead of maintaining the validity of the data
structures and invariants only for the lowest nonempty window, we will
maintain them across all windows, by applying the previous algorithm (with
update time that depends on the aspect ratio) for every window as a black-box,
and the output solution would be the union of all set covers ranging over all
the windows. For efficiency purposes, we would like to somehow map every
element to a single window (instead of up to $f$ windows, one per each set to
which the element belongs), so that for each element update, we will only need
to apply as a black-box our previous dynamic set cover algorithm on that
window, and do nothing for all other windows. Obtaining such a mapping, where
each element is mapped to only one window, is problematic in terms of the
approximation factor. We will not get into this issue, since even ignoring it,
this approach may only give a $(2(1+\epsilon)\ln n)$-approximation, rather
than a $((1+\epsilon)\ln n)$-approximation. Indeed, consider the case where
elements in the lowest window are all lying towards the higher end of the
window; more specifically, assume that in the lowest window of levels
$[0,10\log_{\beta}n]$, all elements are on levels
$[9\log_{\beta}n,10\log_{\beta}n]$. In this case, the costs of sets on levels
$>10\log_{\beta}n$ are not negligible compared to those on levels
$[9\log_{\beta}n,10\log_{\beta}n]$. Consequently, although all sets in the
third lowest window and all higher ones have negligible costs with respect to
the lowest window, we can only argue that the approximation ratios in the two
lowest windows are both $\left((1+\epsilon)\ln n\right)\cdot\mathsf{OPT}$,
which results in a $(2(1+\epsilon)\ln n)$-approximation.

To resolve this issue, we will use two overlapping sequences of windows
instead of one; that is, the first sequence of windows is roughly
$[0,20\log_{\beta}n]\cup[20\log_{\beta}n+1,40\log_{\beta}n]\cup\ldots$, and
the second sequence partitions the levels as roughly
$[0,10\log_{\beta}n],[10\log_{\beta}n+1,30\log_{\beta}n]\cup[30\log_{\beta}n+1,50\log_{\beta}n]\cup\ldots$.
Then, for each of the two partitions, we apply our aspect-ratio-dependent
algorithm as a black-box within each of the windows independently, so in the
end we are maintaining two different candidate set cover solutions, where the
one of smaller cost would be presented to the adversary. We argue that at any
moment, at least one of the candidate set cover solutions provides a
$((1+\epsilon)\ln n)$-approximation. To see this, consider the lowest non-
empty window in each of the two sequences; we can show that in one of those
windows, the lowest non-empty level lies in the lower half of that window, and
the set cover solution corresponding to that window provides the required
approximation, since all sets in the second lowest window and all higher ones
in that sequence have negligible costs with respect to the lowest window, due
to the half-window “buffer” that we have between the lowest nonempty level and
the second window.

Our approach, which employs a fixed partition into windows, has two advantages
over alternative possible suggestions that use dynamically changing windows.
First, it is more challenging to maintain the data structures and the required
invariants when using dynamically changing windows (and it is not even clear
whether such alternative suggestions could work). Second, and perhaps more
importantly, our approach enables us to apply the aspect-ratio-dependent
algorithm as a black-box in each window, whereas it is unclear how to apply
the algorithm as a black-box when using dynamically changing windows. See
Section 4 for details.

##### A Unified Approach.

In Section 5 we demonstrate that our deamortization approach extends
seamlessly to the low-frequency regime. This also applies to the removal of
the aspect ratio dependency from the time bound, which, as mentioned above, is
achieved via a black-box reduction. Our approach thus unifies the landscape of
dynamic set cover algorithms with worst-case time bounds.

##  3 Our Algorithm I: Aspect Ratio Dependence in Update Time

We first prove a weaker version of our result, where the worst-case update
time depends on the aspect ratio.

######  Theorem 3.1.

For any set system $(\mathcal{U},\mathcal{S})$, along with a cost function
$\mathsf{cost}:\mathcal{S}\rightarrow[1/C,1]$, that undergoes a sequence of
element insertions and deletions, where the frequency is always bounded by
$f\geq\ln n$, and for any $\epsilon\in(0,\frac{1}{4})$, there is a dynamic
algorithm that maintains a $((1+\epsilon)\ln n)$-approximate minimum set cover
in $O\left(\frac{f\log(Cn)}{\epsilon^{2}}\right)$ deterministic worst-case
update time.

###  3.1 Preliminaries, Invariants and Approximation Factor Analysis

Without loss of generality, assume that
$\max_{s\in\mathcal{S}}\mathsf{cost}(s)=1$. Let $\beta=1+\epsilon$. All sets
$s\in\mathcal{S}$ will be assigned a level value $\mathsf{lev}(s)\in[-1,L]$
where $L=\lceil\log_{\beta}(Cn)\rceil+\lceil 10\log_{\beta}1/\epsilon\rceil$.
Throughout the algorithm, we will maintain a valid set cover
$\mathcal{S}_{\mathsf{alg}}\subseteq\mathcal{S}$ for all elements. We will
assign each element $e\in\mathcal{U}$ to one of the sets
$s\in\mathcal{S}_{\mathsf{alg}}$, which we will denote by $\mathsf{asn}(e)$,
and conversely, for each set $s\in\mathcal{S}$, define its covering set
$\mathsf{cov}(s)$ to be the collection of elements in $s$ that are assigned to
$s$, namely $\mathsf{cov}(s)=\\{e\mid\mathsf{asn}(e)=s\\}$. The level of an
element $e$ is defined as the level of the set it is assigned to, namely
$\mathsf{lev}(e)=\mathsf{lev}(\mathsf{asn}(e))$, and we make sure that
$\mathsf{lev}(e)=\max\\{lev(s)|s\ni e\\}$, meaning $e$ is assigned to the set
with the highest level containing $e$. We define the level of each set
$s\notin\mathcal{S}_{\mathsf{alg}}$ to be $-1$, whereas the level of each set
$s\in\mathcal{S}_{\mathsf{alg}}$ will lie in $[0,L]$, so in particular we will
have $\mathsf{lev}(e)\in[0,L]$, for each element $e\in\mathcal{U}$. Let
$S_{i}=\\{s\mid\mathsf{lev}(s)=i\\},\forall i\in[-1,L]$, and
$E_{i}=\\{e\in\mathcal{U}\mid\mathsf{lev}(e)=i\\},\forall i\in[0,L]$.

Besides the level value $\mathsf{lev}(e)$ for elements $e$, we will also
maintain a value of _passive level_ $\mathsf{plev}(e)$ such that
$\mathsf{lev}(e)\leq\mathsf{plev}(e)\leq L$, which plays a major role in our
algorithm. In contrast to the level $\mathsf{lev}(e)$ of an element $e$, which
may decrease (as well as increase) by the algorithm, its passive level
$\mathsf{plev}(e)$ will be monotonically non-decreasing throughout its
lifespan.

An element is said to be _dead_ if it was deleted by the adversary, hence it
is supposed to be deleted from $\mathcal{U}$ — but it currently resides in
$\mathcal{U}$ as our algorithm has not removed it yet. An element is said to
be _alive_ if it is not dead. To avoid confusion, we will use the notation
$\mathcal{U}^{+}\supseteq\mathcal{U}$ to denote the set of all dead and alive
elements (i.e., the elements in the view of the algorithm), while
$\mathcal{U}$ is the set of alive elements (i.e., the elements in the eye of
the adversary). We next introduce the following key definitions.

######  Definition 3.1.

For each level $k$, an element $e\in\mathcal{U}^{+}$ is called _$k$ -active_
(respectively, _$k$ -passive_) if $\mathsf{lev}(e)\leq k<\mathsf{plev}(e)$
(resp., $\mathsf{plev}(e)\leq k$) and let
$A_{k}=\\{e\in\mathcal{U}^{+}\mid\mathsf{lev}(e)\leq k<\mathsf{plev}(e)\\}$
and $P_{k}=\\{e\in\mathcal{U}^{+}\mid\mathsf{plev}(e)\leq k\\}$ be the sets of
all $k$-active and $k$-passive elements, respectively. Notice that $A_{k}\cup
P_{k}$ is the collection of all elements at level $\leq k$, and $A_{k}\cap
P_{k}=\emptyset$. Moreover, if $A_{k}\cap P_{j}\neq\emptyset$ for two levels
$k\neq j$, then $k<j$. For each set $s\in\mathcal{S}$, define
$N_{k}(s)=A_{k}\cap s$.

While previous works on primal-dual dynamic set cover algorithms [BHN19,
BHNW21, BSZ23] also use the terminology of active and passive elements, it has
a completely different meaning there. Moreover, importantly, while in previous
work an element may be either active or passive, here we refine this binary
distinction by introducing a level parameter; in particular, an element might
be $k$-active and yet $j$-passive (for indices $k<j$).

This refinement is crucial for our algorithm to efficiently maintain the
following invariant (Invariant 3.1), which is key to bounding the
approximation factor (see Lemma 3.1 and Corollary 3.1). The first part of the
invariant essentially aims at achieving a global analog of the local 2.2(2).
It actually provides a strict upper bound on $|N_{k}(s)|$ for any set $s$ and
each level $k$, which might seem too good to be true. The reason such a
strict, local upper bound can be efficiently maintained by the algorithm is
that $N_{k}(s)$ is restricted to the $k$-active elements in set $s$, or in
other words, _all $k$-passive elements in $s$ are simply ignored_ — which is
where the global relaxation comes into play. Indeed, to prevent the
accumulation of too many $k$-passive elements — which is crucial for bounding
the approximation ratio — the third part of the invariant restricts the ratio
between the $k$-passive elements and the $k$-active elements to be at most
$2\epsilon$ at all times. Thus, although the upper bound on $|N_{k}(s)|$ holds
“locally” (i.e., for any set $s$ and each level $k$), it only holds “globally”
(i.e., for an average set and each level $k$) if we take into account the
ignored $k$-passive elements. In order for the algorithm to maintain the third
part of the invariant, a natural thing to do would be to turn $k$-passive
elements into active across all levels (or _fully-active_). Alas, if we turned
a $k$-passive element into fully-active, that could violate the first part of
the invariant across multiple levels. To circumvent this hurdle, our algorithm
will turn elements into _partially-active_ , i.e., active in a precise
interval of levels; specifically, element $e$ will become active in the
interval $[\mathsf{lev}(e),\mathsf{plev}(e)-1]$ (as in Definition 3.1), and to
perform efficiently — the algorithm will have to carefully choose the right
values for $\mathsf{lev}(e)$ and $\mathsf{plev}(e)$; the exact details are
given in the algorithm’s description (Section 3.2). Finally, we note that the
second part of Invariant 3.1 coincides with 2.2(1). Here too, the invariant
seems like a local bound since it holds for any $s$, but it uses again the
global relaxation provided by the third part of the invariant, since it
considers dead elements as well.

######  Invariant 3.1.

  1. (1)

For any set $s\in\mathcal{S}$ and for each $k\in[0,L]$, we have
$\frac{|N_{k}(s)|}{\mathsf{cost}(s)}<\beta^{k+1}$.

  2. (2)

For any set $s\in\mathcal{S}_{\mathsf{alg}}$, we have
$\frac{|\mathsf{cov}(s)|}{\mathsf{cost}(s)}\geq\beta^{\mathsf{lev}(s)}$; we
note that $\mathsf{cov}(s)$ may include dead elements, i.e., elements in
$\mathcal{U}^{+}\setminus\mathcal{U}$. In particular,
$\mathsf{lev}(s)\leq\lceil\log_{\beta}(Cn)\rceil$. Moreover, for each
$s\notin\mathcal{S}_{\mathsf{alg}}$, $\mathsf{lev}(s)=-1$.

  3. (3)

For each $k\in[0,L]$, we have $|P_{k}|\leq 2\epsilon\cdot|A_{k}|$. We note
that our algorithm does not maintain the values of $|P_{k}|,|A_{k}|$.

The following lemma shows that the approximation factor is in check (the term
$1+O(\epsilon)$ can be reduced to $1+\epsilon$ by scaling). The proof of Lemma
3.1 is inherently different from and more challenging than the approximation
factor proofs of the previous dynamic greedy set cover algorithms [GKKP17,
SU23]; while the proofs of [GKKP17, SU23] are obtained by introducing natural
tweaks over the standard analysis of the static greedy algorithm, our
approximation factor proof has to deviate significantly from the standard
paradigm, since 3.1 is inherently weaker than those of [GKKP17, SU23] —
particularly as 3.1(1) ignores all $k$-passive elements.

######  Lemma 3.1.

Let $\mathcal{S}^{*}$ be an optimal set cover for $\mathcal{U}$ (i.e., of all
alive elements), and let $n^{\prime}$ be an upper bound to the size of each
set throughout the update sequence. If 3.1 is satisfied, then it holds that
$\mathsf{cost}(\mathcal{S}_{\mathsf{alg}})\leq(1+O(\epsilon))\cdot\ln
n^{\prime}\cdot\mathsf{cost}(\mathcal{S}^{*})$.

###### Proof.

By 3.1(3), we have for all $k\in[0,L-1]$:

$\left(\beta^{-k}-\beta^{-k-1}\right)\cdot|P_{k}|~{}\leq~{}2\epsilon\cdot\left(\beta^{-k}-\beta^{-k-1}\right)\cdot|A_{k}|.$
(1)

Taking a summation over all $k\in\left[0,L-1\right]$, the left-hand side of
Equation 1 becomes:

$\displaystyle\sum_{k=0}^{L-1}(\beta^{-k}-\beta^{-k-1})\cdot|P_{k}|$
$\displaystyle=\sum_{e\in\mathcal{U}^{+}}\sum_{k=0}^{L-1}(\beta^{-k}-\beta^{-k-1})\cdot\mathbf{1}[e\in
P_{k}]$
$\displaystyle=\sum_{e\in\mathcal{U}^{+}}\sum_{k=\mathsf{plev}(e)}^{L-1}(\beta^{-k}-\beta^{-k-1})$
$\displaystyle=\sum_{e\in\mathcal{U}^{+}}\left(\beta^{-\mathsf{plev}(e)}-\beta^{-L}\right)$

and the right-hand side of Equation 1 becomes:

$\displaystyle 2\epsilon\sum_{k=0}^{L-1}(\beta^{-k}-\beta^{-k-1})\cdot|A_{k}|$
$\displaystyle=2\epsilon\sum_{e\in\mathcal{U}^{+}}\sum_{k=0}^{L-1}(\beta^{-k}-\beta^{-k-1})\cdot\mathbf{1}[e\in
A_{k}]$
$\displaystyle=2\epsilon\sum_{e\in\mathcal{U}^{+}}\sum_{k=\mathsf{lev}(e)}^{\mathsf{plev}(e)-1}(\beta^{-k}-\beta^{-k-1})$
$\displaystyle=2\epsilon\sum_{e\in\mathcal{U}^{+}}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)}\right),$

which yields:

$\sum_{e\in\mathcal{U}^{+}}\left(\beta^{-\mathsf{plev}(e)}-\beta^{-L}\right)\leq
2\epsilon\cdot\sum_{e\in\mathcal{U}^{+}}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)}\right)$

or equivalently, by adding
$\sum_{e\in\mathcal{U}^{+}}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)}\right)$
on the both sides,

$\sum_{e\in\mathcal{U}^{+}}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-L}\right)~{}\leq~{}(1+2\epsilon)\cdot\sum_{e\in\mathcal{U}^{+}}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)}\right).$
(2)

We emphasize the point that $\mathcal{U}^{+}$ also includes dead elements.

Next, let us lower bound $\mathsf{cost}(\mathcal{S}^{*})$ using the term
$\sum_{e\in\mathcal{U}^{+}}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)}\right)$.
For any $s\in\mathcal{S}^{*}$, consider the following three cases for any
index $k\in[L]$:

  * •

$k<\log_{\beta}(1/\mathsf{cost}(s))-1$.

By 3.1(1), we have: $|N_{k}(s)|<\beta^{k+1}\cdot\mathsf{cost}(s)<1$, so
$|N_{k}(s)|=0$.

  * •

$\log_{\beta}(1/\mathsf{cost}(s))-1\leq
k\leq\log_{\beta}(n^{\prime}/\mathsf{cost}(s))$.

By 3.1(1), we have:

$\frac{1}{\epsilon}\left(\beta^{-k}-\beta^{-k-1}\right)|N_{k}(s)|=\beta^{-k-1}|N_{k}(s)|<\mathsf{cost}(s).$

  * •

$k>\lceil\log_{\beta}(n^{\prime}/\mathsf{cost}(s))\rceil=k_{0}$.

In this case, we use the trivial bound: $|N_{k}(s)|\leq
n^{\prime}\leq\beta^{k_{0}}\cdot\mathsf{cost}(s)$, and so we have:

$\frac{1}{\epsilon}\left(\beta^{-k}-\beta^{-k-1}\right)|N_{k}(s)|=\beta^{-k-1}|N_{k}(s)|\leq\beta^{k_{0}-k-1}\cdot\mathsf{cost}(s).$

Observe that:

$\displaystyle\frac{1}{\epsilon}\sum_{k=0}^{L-1}(\beta^{-k}-\beta^{-k-1})\cdot|N_{k}(s)|$
$\displaystyle=\frac{1}{\epsilon}\sum_{e\in
s}\sum_{k=0}^{L-1}(\beta^{-k}-\beta^{-k-1})\cdot\mathbf{1}[e\in N_{k}(s)]$ (3)
$\displaystyle=\frac{1}{\epsilon}\sum_{e\in
s}\sum_{k=\mathsf{lev}(e)}^{\mathsf{plev}(e)-1}(\beta^{-k}-\beta^{-k-1})$
$\displaystyle=\frac{1}{\epsilon}\sum_{e\in
s}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)}\right).$

By the above case analysis, we have:

$\displaystyle\frac{1}{\epsilon}\sum_{k=0}^{L-1}(\beta^{-k}-\beta^{-k-1})\cdot|N_{k}(s)|$
$\displaystyle=\frac{1}{\epsilon}\sum_{0\leq
k<\log_{\beta}(1/\mathsf{cost}(s))-1}(\beta^{-k}-\beta^{-k-1})\cdot|N_{k}(s)|$
(4)
$\displaystyle~{}~{}~{}+\frac{1}{\epsilon}\sum_{\log_{\beta}(1/\mathsf{cost}(s))-1\leq
k\leq\log_{\beta}(n^{\prime}/\mathsf{cost}(s))}(\beta^{-k}-\beta^{-k-1})\cdot|N_{k}(s)|$
$\displaystyle~{}~{}~{}+\frac{1}{\epsilon}\sum_{\log_{\beta}(n^{\prime}/\mathsf{cost}(s))<k\leq
L-1}(\beta^{-k}-\beta^{-k-1})\cdot|N_{k}(s)|$ $\displaystyle<\sum_{0\leq
k<\log_{\beta}(1/\mathsf{cost}(s))-1}0$
$\displaystyle~{}~{}~{}+\sum_{\log_{\beta}(1/\mathsf{cost}(s))-1\leq
k\leq\log_{\beta}(n^{\prime}/\mathsf{cost}(s))}\mathsf{cost}(s)$
$\displaystyle~{}~{}~{}+\sum_{\log_{\beta}(n^{\prime}/\mathsf{cost}(s))<k\leq
L-1}\beta^{k_{0}-k-1}\mathsf{cost}(s)$
$\displaystyle<\left(0+(\log_{\beta}(n^{\prime})+2)+1/\epsilon\right)\cdot\mathsf{cost}(s).$

Combining Equation 3 with Equation 4 yields

$\frac{1}{\epsilon}\sum_{e\in
s}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)}\right)\leq\left(\log_{\beta}(n^{\prime})+2+1/\epsilon\right)\cdot\mathsf{cost}(s).$

Therefore, as $\ln(1+\epsilon)=\epsilon+O(\epsilon^{2})$, under the assumption
that $\epsilon=\Omega(1/\log n^{\prime})$ we have:

$\sum_{e\in
s}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)}\right)\leq(1+O(\epsilon))\ln
n^{\prime}\cdot\mathsf{cost}(s).$

Since $\mathcal{S}^{*}$ is a valid set cover for all elements in $\mathcal{U}$
(all the alive elements) and as for each dead element $e$ (in
$\mathcal{U}^{+}\setminus\mathcal{U}$) we have
$\left(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)}\right)=0$, it
follows that:

$\sum_{e\in\mathcal{U}^{+}}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)}\right)~{}\leq~{}\sum_{s\in
S^{*}}\sum_{e\in
s}(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)})~{}\leq~{}(1+O(\epsilon))\ln
n^{\prime}\cdot\mathsf{cost}(\mathcal{S}^{*}).$ (5)

We conclude that

$\displaystyle\mathsf{cost}(\mathcal{S}_{\mathsf{alg}})$
$\displaystyle=\sum_{s\in\mathcal{S}_{\mathsf{alg}}}\mathsf{cost}(s)\leq\sum_{s\in\mathcal{S}_{\mathsf{alg}}}\beta^{-\mathsf{lev}(s)}\cdot|\mathsf{cov}(s)|~{}=~{}\beta\cdot\sum_{s\in\mathcal{S}_{\mathsf{alg}}}\sum_{e\in\mathsf{cov}(s)\cap\mathcal{U}^{+}}\beta^{-\mathsf{lev}(e)}$
$\displaystyle\leq(1+O(\epsilon))\cdot\sum_{e\in\mathcal{U}^{+}}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-L}\right)~{}\leq~{}(1+O(\epsilon))\cdot\sum_{e\in\mathcal{U}^{+}}\left(\beta^{-\mathsf{lev}(e)}-\beta^{-\mathsf{plev}(e)}\right)$
$\displaystyle\leq(1+O(\epsilon))\ln
n^{\prime}\cdot\mathsf{cost}(\mathcal{S}^{*}),$

where the first inequality holds by 3.1(2), the second holds as
$\mathsf{lev}(e)\leq L/2$ and hence
$\beta^{-\mathsf{lev}(e)}-\beta^{-L}\geq\beta^{-\mathsf{lev}(e)}(1-\beta^{-\lceil
10\log_{\beta}1/\epsilon\rceil})\geq\beta^{-\mathsf{lev}(e)}(1-\epsilon)$, and
the last two follow from Equation 2 and Equation 5, respectively. ∎

######  Corollary 3.1.

Since $n^{\prime}\leq n$, we get that if 3.1 is satisfied, then it holds that
$\mathsf{cost}(\mathcal{S}_{\mathsf{alg}})\leq(1+O(\epsilon))\cdot\ln
n\cdot\mathsf{cost}(\mathcal{S}^{*})$.

###  3.2 Algorithm Description

We will skip the details for the fully global algorithm that maintains 3.1,
with _amortized_ update time of $O(\frac{f\cdot\log(Cn)}{\epsilon^{2}})$; for
the general outline of this algorithm, see Section 2.2.1. Instead, we will
dive straight into our ultimate goal of providing an algorithm that maintains
3.1, with a _worst-case_ update time of
$O(\frac{f\cdot\log(Cn)}{\epsilon^{2}})$ — this is the result that underlies
Theorem 3.1. The main procedure of the algorithm is a reset operation, denoted
by $\mathsf{reset}(k)$ when initiated for a level $k$. Simply put, performing
a reset to level $k$ amounts to running the static greedy algorithm on the
subuniverse of elements and sets at level up to $k$. Our algorithm
distinguishes between procedures and data structures that are executed and
maintained in the _foreground_ and those in the _background_. The foreground
procedures can be executed from start to finish between one adversarial update
step to the next — and as such are very basic procedures, and the foreground
data structures support the foreground procedures and are used for explicitly
maintaining the output solution at every update step. In contrast, the
background procedures can take a long time to run; the algorithm simulates
their execution over a possibly long time interval in the background, and only
upon termination of the execution, the main algorithm may “copy” the
background data structures and their induced output into the foreground data
structures and their induced output. In particular, the aforementioned reset
operation will be running in the background, while adversarial insertions and
deletions will be handled in a rather straightforward manner in the
foreground. We note that for an amortized algorithm, there is no need for any
background procedures, since everything can be executed on the foreground when
needed. Meaning, once a reset needs to be executed, we just execute it in a
single update step in the foreground. In this section we give a high level
description of the algorithm, refer to Section 3.3 for more lower level
details regarding the exact data structures maintained etc.

####  3.2.1 Foreground

The set cover solution $\mathcal{S}_{\mathsf{alg}}$, which serves as the
interface to the adversary (i.e., the output), will be maintained in the
foreground. Element deletions and insertions will be handled in the foreground
as follows.

  * •

Deletions in the Foreground. When an element $e\in\mathcal{U}$ is deleted by
the adversary, we set $\mathsf{plev}(e)\leftarrow\mathsf{lev}(e)$, and mark
element $e$ as dead. Finally, for each $k\geq\mathsf{lev}(e)$, we feed the
deletion of $e$ to instance $\mathsf{reset}(k)$ (if operating). Note that
there is no need to feed the deletion of $e$ to instances of
$\mathsf{reset}(k)$ with $k\leq\mathsf{lev}(e)-1$, since $\mathsf{reset}(k)$
is not affected by (and does not affect) levels larger than $k+1$. See
Algorithm 1 for the pseudo-code.

1 $\mathsf{plev}(e)\leftarrow\mathsf{lev}(e)$;

2 mark $e$ as dead;

3 for  _$k$ from $\mathsf{lev}(e)$ to $L$_ do

4 if  _$\mathsf{reset}(k)$ is operating_ then

5 feed this deletion of $e$ to background system working on
$\mathsf{reset}(k)$;

6

Algorithm 1 $\textsf{Foreground-Delete}(e)$

  * •

Insertions in the Foreground. When an element $e$ is inserted by the
adversary, go over all sets $s\ni e$ and check if there is one in our set
cover solution $\mathcal{S}_{\mathsf{alg}}$. If so, let $s\ni e$ be such a set
at the highest level, and assign
$\mathsf{lev}(e)=\mathsf{plev}(e)=\mathsf{lev}(s),\mathsf{asn}(e)=s$. If $e$
is not covered by any set currently in $\mathcal{S}_{\mathsf{alg}}$, add an
arbitrary $s\in\mathcal{S}\setminus\mathcal{S}_{\mathsf{alg}}$ to
$\mathcal{S}_{\mathsf{alg}}$, (which was at level $-1$, as guaranteed by
3.1(2)), and assign
$\mathsf{plev}(e)=\mathsf{lev}(e)=\mathsf{lev}(s)=0,\mathsf{asn}(e)=s$. (Note
that after adding $s$ to $\mathcal{S}_{\mathsf{alg}}$, 3.1(2) is still
satisfied, as $\frac{|\mathsf{cov}(s)|}{\mathsf{cost}(s)}\geq
1=\beta^{\mathsf{lev}(s)}$.) Finally, for each $k\geq\mathsf{plev}(e)$, feed
the insertion $e$ to instance $\mathsf{reset}(k)$ if operating. See Algorithm
2 for the pseudo-code, and Figure 2 for an illustration of a deletion and
insertion.

1 let $s\ni e$ be highest level set containing $e$;

2 if  _$\mathsf{lev}(s) >-1$_ then

3 $\mathsf{lev}(e),\mathsf{plev}(e)\leftarrow\mathsf{lev}(s)$;

4 $\mathsf{asn}(e)\leftarrow s$;

5

6else

7 $\mathsf{lev}(e),\mathsf{plev}(e),\mathsf{lev}(s)\leftarrow 0$;

8 $\mathsf{asn}(e)\leftarrow s$;

9 $\mathcal{S}_{\mathsf{alg}}\leftarrow\mathcal{S}_{\mathsf{alg}}\cup\\{s\\}$;

10

11for  _$k$ from $\mathsf{plev}(e)$ to $L$_ do

12 if  _$\mathsf{reset}(k)$ is operating_ then

13 feed this insertion of $e$ to background system working on
$\mathsf{reset}(k)$;

14

Algorithm 2 $\textsf{Foreground-Insert }(e)$ Figure 2:  $3$-active (green) and
$3$-passive (red) elements at time $t$ (left), $t+1$ (middle) and $t+2$
(right). Between $t$ and $t+1$ the element at level $2$ is deleted, thus
becomes $3$-passive (because its passive level becomes $2$). Between $t+1$ and
$t+2$, an element is inserted to level 1. It is $3$-passive because its
passive level is $1$.

  * •

Termination of $\mathsf{reset}(\cdot)$ Instances. Upon any element update
(deletion or insertion), go over all levels $0\leq k\leq O(\log_{\beta}(Cn))$
and check if any instance $\mathsf{reset}(k)$ has just terminated right after
the update. If so, take the largest such index $k$, and switch its memory to
the foreground; we will describe how a memory switch is done later on in
Section 3.3.4. After that, abort all instances of $\mathsf{reset}(i)$, for
$0\leq i<k$.

  * •

Initiating $\mathsf{reset}(\cdot)$ Instances. Upon any element update
(deletion or insertion), go over all levels $0\leq k\leq L$ and check if there
is currently an instance $\mathsf{reset}(k)$. Denote by
$k_{1},k_{2},k_{3},\ldots$ the levels that do not have such an instance, where
$k_{1}<k_{2}<k_{3}<\ldots$. Next, we want to partition all levels $k_{i}$ into
_short levels_ and _non-short levels_. All of the short levels will be lower
than the non-short levels, meaning exists $i$ such that $k_{i^{\prime}}$ is a
short level for any $i^{\prime}<i$ and a non-short level for any
$i^{\prime}\geq i$. In a nutshell, we will be able to execute a short level
reset in a single update step, since the number of elements participating in
the reset is small enough. Recall that upon termination of a reset we abort
all instances of lower level resets, thus there is no reason to run all short
level resets, only the highest one. Regarding the non-short levels, we
initiate a reset to each and every one of them. To find the highest short
level given $k_{1},k_{2},k_{3},\ldots$ we do as follows. First, count all the
first $\frac{L}{f}$ elements, from level $0$ upwards. Say that the
$\frac{L}{f}$-th element is at level $j$. Thus, we know that
$|\bigcup_{i=0}^{j^{\prime}}E_{i}|<\frac{L}{f}$ for any $0\leq j^{\prime}<j$.
Define $i$ to be the highest such that $k_{i}<j$. If no such $i$ exists then
there are no short levels, otherwise $k_{i}$ is the highest short level, and
we initiate the resets for levels $k_{i},k_{i+1},\ldots$, where again $k_{i}$
is a short level and the rest are non-short levels.

####  3.2.2 Background

For each level $k\in[0,L]$, any reset instance $\mathsf{reset}(k)$ that
operates (in the background) maintains a partial copy of the foreground in the
background. Specifically, we maintain and define the following:

  1. (1)

We maintain subsets of elements
$\mathcal{U}^{(k)},\mathcal{U}^{(k)+}\subseteq\mathcal{U}^{+}$
($\mathcal{U}^{(k)}$ are the alive elements in $\mathcal{U}^{(k)+}$), and for
each element $e\in\mathcal{U}^{(k)+}$, maintain the two level indices
$\mathsf{lev}^{(k)}(e)$ and $\mathsf{plev}^{(k)}(e)$. In addition, we maintain
a subset of sets $\mathcal{S}^{(k)}\subseteq\mathcal{S}$, and a level value
$\mathsf{lev}^{(k)}(s)$ for each $s\in\mathcal{S}^{(k)}$, as well as a partial
set cover solution $\mathcal{S}^{(k)}_{\mathsf{alg}}$ that covers all elements
in $\mathcal{U}^{(k)}$

  2. (2)

For each level $i\in[-1,k+1]$, let
$S_{i}^{(k)}=\\{s\mid\mathsf{lev}^{(k)}(s)=i\\}$ and for each level
$i\in[0,k+1]$, let $E_{i}^{(k)}=\\{e\mid\mathsf{lev}^{(k)}(e)=i\\}$.

  3. (3)

For each element $e\in\mathcal{U}^{(k)}$, we maintain the assignment
$\mathsf{asn}^{(k)}(e)\in\mathcal{S}^{(k)}_{\mathsf{alg}}$, and for each set
$s\in\mathcal{S}$ maintain the set $\mathsf{cov}^{(k)}(s)$, where
$\mathsf{cov}^{(k)}(s)=\\{e\mid\mathsf{asn}^{(k)}(e)=s\\}$.

######  Definition 3.2.

The procedure $\mathsf{reset}(k)$ could make two different types of steps,
_immediate_ and _planned_ : An immediate step of the algorithm is executed
right away, whereas a planned step of the algorithm is stored implicitly in
the background, and only executed when scheduled by the main algorithm in the
foreground in reaction to element updates.

As mentioned, for each level $k$, if there is currently no instance
$\mathsf{reset}(k)$, then we start an instance $\mathsf{reset}(k)$ in the
background if $k$ is either a non-short level or it is the highest short
level. Then, after each adversarial update step, go over all non-short levels
$k\in[0,L]$, and execute $O\left(f/\epsilon\right)$ _planned_ steps (see
Definition 3.2) of each instance of $\mathsf{reset}(k)$ (if operating), and
execute the full reset of the short level reset. Roughly speaking, during the
execution of an instance of $\mathsf{reset}(k)$, if an element is inserted or
deleted on some level in the range $[0,k]$, then the background procedure
$\mathsf{reset}(k)$ should also handle it. When an instance of
$\mathsf{reset}(k)$ terminates, it will update all information on levels $\leq
k$, and partly on level $k+1$, and then abort all other instances of
$\mathsf{reset}(i),i<k$. The main technical part of our algorithm is the
procedure $\mathsf{reset}(k)$, which runs in the background. Next, we describe
the reset procedure, which consists of three phases: (I) initialization, (II)
greedy set cover algorithm, and (III) termination.

##### Phase I: Initialization.

When an instance of $\mathsf{reset}(k)$ has been initiated by the foreground,
it sets the following:

  * •

$\mathcal{S}^{(k)}_{\mathsf{alg}}=S_{i}^{(k)}\leftarrow\emptyset,\forall
i\in[0,k+1]$.

  * •

$E_{i}^{(k)}\leftarrow\emptyset,\forall i\in[0,k+1]$

  * •

$\mathcal{U}^{(k)}=\mathcal{U}^{(k)+}\leftarrow(\bigcup_{i=0}^{k}E_{i})\cap\mathcal{U}$.
Meaning, the elements participating in the reset are the alive elements up to
level $k$ in the foreground.

  * •

$\mathcal{S}^{(k)}\leftarrow$ all sets that contain an element in
$\mathcal{U}^{(k)}$. Note that we cannot create $\mathcal{S}^{(k)}$ directly
from the sets $S_{k},S_{k-1},\cdots,S_{-1}$, as there might be several sets at
level $-1$ not containing any element in $\mathcal{U}^{(k)}$, and we do not
want these sets to participate in a reset, since it could blow up the update
time.

  * •

$\mathsf{lev}^{(k)}(e)\leftarrow-1,\forall e\in\mathcal{U}^{(k)}$

  * •

$\mathsf{plev}^{(k)}(e)\leftarrow\max\\{\mathsf{plev}(e),k+1\\},\forall
e\in\mathcal{U}^{(k)}$. Intuitively, following a reset to $k$ we want all
elements participating in this reset ($\mathcal{U}^{(k)}$) to be active up to
at least $k+1$ (without decreasing).

  * •

$\mathsf{lev}^{(k)}(s)\leftarrow-1,\forall s\in\mathcal{S}^{(k)}$

While the level $\mathsf{lev}^{(k)}(e)$ of elements $e$, initialized as $-1$,
will be assigned a value from $0$ to $k+1$ throughout the execution of
$\mathsf{reset}(k)$, the passive level $\mathsf{plev}^{(k)}(e)$ is assigned a
value during initialization and does not change throughout the execution of
$\mathsf{reset}(k)$. We note that $\mathsf{plev}^{(k)}(e)$ is no smaller than
the foreground passive level $\mathsf{plev}(e)$ of any element $e$, which will
guarantee that the passive level of an element is monotone non-decreasing.
Moreover, $\mathsf{plev}^{(k)}(e)$ is at least $k+1$, which will guarantee
that none of the elements that participate in $\mathsf{reset}(k)$ from the
initialization may belong to $P_{i}$, for any level $i\leq k$. In addition,
there is no effect to any level $j>k+1$, meaning if an element $e$ was
$j$-passive before the reset to $k$, it will still be after, and if it was
$j$-active, it will still be after. For each set $s\in\mathcal{S}^{(k)}$, we
store the set $s\cap\mathcal{U}^{(k)}$ (in a linked list). The stated steps
incur a high running time, and as such cannot be executed in the foreground as
immediate steps before the next update step occurs (aiming for a low worst-
case update time), hence they will be scheduled as planned steps in the
background. For any new element $e$ that is inserted by the adversary during
the initialization, we assign $\mathsf{lev}^{(k)}(e)=-1$ and
$\mathsf{plev}^{(k)}(e)\leftarrow k+1$; for any old element
$e\in\mathcal{U}^{(k)+}$ that is deleted by the adversary during the
initialization, and as such becomes dead, we remove it from
$\mathcal{U}^{(k)}$. Specific implementation of this phase is described in
Section 3.3.2.

##### Phase II: Greedy Set Cover Algorithm.

The algorithm consists of $k+2$ rounds, iterating from level $i=k+1$ down to
$i=0$; in what follows, by writing “the $i$th round” we refer to the round
that corresponds to level $i$. During the process, the algorithm maintains a
collection $U\subseteq\mathcal{U}^{(k)}$, which is the collection of all alive
elements that have not been covered yet by the gradually growing
$\mathcal{S}^{(k)}_{\mathsf{alg}}$, and for each set
$s\in\mathcal{S}^{(k)}\setminus\mathcal{S}^{(k)}_{\mathsf{alg}}$, it maintains
all elements in $s\cap U$ (in a linked list). At the beginning of the $i$th
round, we make the assumption below, which will be proven in 3.1.2.

######  Assumption 3.1.

The following two conditions hold at the beginning of the $i$th round.
Importantly, these conditions do not necessarily hold throughout the $i$th
round.

  * •

All elements in $U$ are alive; this holds for any round $i=k+1,\ldots,0$.

  * •

For any round $i=k,\ldots,0$, $|s\cap U|/\mathsf{cost}(s)<\beta^{i+1}$; for
$i=k+1$, there is no upper bound on $|s\cap U|/\mathsf{cost}(s)$.

During the $i$th round, the following steps will be scheduled as planned.

Planned Steps in the $i$th Round. During the $i$th round, the algorithm
iteratively chooses a set
$s\in\mathcal{S}^{(k)}\setminus\mathcal{S}^{(k)}_{\mathsf{alg}}$ that
maximizes $|s\cap U|/\mathsf{cost}(s)$ such that $|s\cap
U|/\mathsf{cost}(s)\geq\beta^{i}$. This will be implemented by a _truncated
max-heap_ (see Section 3.3.3 for details). If no such $s$ exists and $i>0$, we
proceed to the next ($i-1$) round. Add $s$ to
$\mathcal{S}^{(k)}_{\mathsf{alg}}$, assign $\mathsf{lev}^{(k)}(s)\leftarrow
i$, and then go over all alive elements $e\in s\cap U$ and assign
$\mathsf{lev}^{(k)}(e)\leftarrow i,\mathsf{asn}^{(k)}(e)\leftarrow s$; note
that $\mathsf{plev}^{(k)}(e)$ was already assigned for elements that existed
at the beginning of this phase, and, as described below, it is also assigned
for newly inserted elements. After that, we remove $e$ from $U$ and enumerate
all sets $s^{\prime}\ni e$ to maintain $s^{\prime}\cap U$.

See Algorithm 3 for the pseudo-code of the planned steps in the greedy set
cover algorithm.

1 for  _$i$ from $k+1$ to 0_ do

2 NoSets $\leftarrow$ FALSE;

3 while  _(!NoSets)_ do

4 choose a set
$s\in\mathcal{S}^{(k)}\setminus\mathcal{S}^{(k)}_{\mathsf{alg}}$ that
maximizes $|s\cap U|/\mathsf{cost}(s)$;

5 if  _( $|s\cap U|/\mathsf{cost}(s)<\beta^{i}$) _or_
($\mathcal{S}^{(k)}\setminus\mathcal{S}^{(k)}_{\mathsf{alg}}=\emptyset$)_ then

6 NoSets $\leftarrow$ TRUE;

7

8 else

9
$\mathcal{S}^{(k)}_{\mathsf{alg}}\leftarrow\mathcal{S}^{(k)}_{\mathsf{alg}}\cup\\{s\\}$;

10 $\mathsf{lev}^{(k)}(s)\leftarrow i$;

11 for  _$e\in s\cap U$_ do

12 $\mathsf{lev}^{(k)}(e)\leftarrow i$;

13 $\mathsf{asn}^{(k)}(e)\leftarrow s$;

14 $U\leftarrow U\setminus\\{e\\}$;

15 for  _$s^{\prime}\ni e$_ do

16 $s^{\prime}\cap U\leftarrow s^{\prime}\cap U\setminus\\{e\\}$;

17 Update heap;

18

Algorithm 3 Phase II of $\mathsf{reset}(k)$ \- Greedy Set Cover Algorithm

Finally, we describe how to handle adversarial element updates that are fed to
the background during the $i$th round.

  * •

Deletions in the Background. Suppose that an element $e$ is deleted by the
adversary during the $i$th round. We mark $e$ as dead (thus it joins
$\mathcal{U}^{(k)+}\setminus\mathcal{U}^{(k)}$), and assign
$\mathsf{plev}^{(k)}(e)\leftarrow\mathsf{lev}^{(k)}(e)$. If $e$ is in $U$ at
the moment, we remove $e$ from $U$, enumerate all sets $s\ni e$, update the
linked list $s\cap U$, and update the truncated max-heap.

  * •

Insertions in the Background. Suppose that an element $e$ is inserted by the
adversary during the $i$th round. Enumerate all sets $s\ni e$, and proceed as
follows:

    * –

If $e$ belongs to a set in $\mathcal{S}^{(k)}_{\mathsf{alg}}$ (and thus
covered by $\mathcal{S}^{(k)}_{\mathsf{alg}}$), then find such a set
$s\in\mathcal{S}^{(k)}_{\mathsf{alg}}$ that maximizes $\mathsf{lev}^{(k)}(s)$,
and then assign
$\mathsf{lev}^{(k)}(e)=\mathsf{plev}^{(k)}(e)\leftarrow\mathsf{lev}^{(k)}(s)$.
Note that such elements will not have $\mathsf{plev}^{(k)}\geq k+1$ as
elements that exist at the beginning of the execution of $\mathsf{reset}(k)$.

    * –

Otherwise, $e$ is not covered by $\mathcal{S}^{(k)}_{\mathsf{alg}}$, in which
case we assign $\mathsf{plev}^{(k)}(e)\leftarrow
i,\mathsf{lev}^{(k)}(e)\leftarrow-1$. Such elements might be covered
throughout this or subsequent rounds of $\mathsf{reset}(k)$, which will change
their $\mathsf{lev}^{(k)}(e)$ to be the round in which they are covered, i.e.,
at most $i$, but their $\mathsf{plev}^{(k)}(e)$ will remain $i$; note also the
difference from elements that existed at the beginning of the execution of
$\mathsf{reset}(k)$.

    * –

Regardless of whether $e$ belongs to a set in
$\mathcal{S}^{(k)}_{\mathsf{alg}}$ or not, we need to add all sets not in
$\mathcal{S}^{(k)}$ containing $e$ to
$\mathcal{S}^{(k)}\setminus\mathcal{S}^{(k)}_{\mathsf{alg}}$. There are at
most $f$ such sets, and for each such set $s^{\prime}$ we know that
$s^{\prime}\cap U=\\{e\\}$, since otherwise $s^{\prime}$ would have already
been in $\mathcal{S}^{(k)}$. Therefore, we can update the heap in $O(f)$ time
following the insertion of $e$.

##### Phase III: Termination.

When all $(k+2)$ rounds of the greedy set cover algorithm terminate, we set
$S_{i}$ and $E_{i}$ (foreground) to be $S_{i}^{(k)}$ and $E^{(k)}_{i}$,
respectively, for each $i\in[0,k]$. Then, append the linked list of
$S_{k+1}^{(k)}$ and $E_{k+1}^{(k)}$ to $S_{k+1}$ and $E_{k+1}$. Finally, we
abort all lower-level reset instances. Specific implementation is described in
Section 3.3.4.

###  3.3 Implementation Details and Update Time Analysis

In this section we will describe the maintained data structures and analyze
the worst-case update time for each part of the algorithm separately.

Data Structures that Link between the Foreground and Background.

  1. (a)

For each $k$, we have pointers to the sets $S^{(k)}_{i}$ and $E^{(k)}_{i}$,
stored in two arrays of size $L+2$ and $L+1$, respectively (an entry for every
$i\in[-1,L]$ and $i\in[0,L]$, respectively). In addition, the head of the list
$S^{(k)}_{i}$ and $E^{(k)}_{i}$ keeps a Boolean value which indicates whether
it is in the foreground or not.

  2. (b)

We store an array in the foreground $\mathsf{lev}[\cdot]$ indexed by
$s\in\mathcal{S}$ and $e\in\mathcal{U}$. So the size of this array should be
$O(|\mathcal{S}|+|\mathcal{U}|)$. Here we have assumed that sets and elements
have unique identifiers from a small integer universe (if the sets and
elements belong to a large integer universe and assuming we would like to
optimize the space usage, we can use hash tables instead of arrays). For each
$s\in\mathcal{S}$ and $0\leq k\leq L$, $\mathsf{lev}[s][k]$ stores a pointer
to the memory location containing the value of $\mathsf{lev}^{(k)}(s)$, as
well as a pointer to the list head of $S^{(k)}_{i}$ if
$\mathsf{lev}^{(k)}(s)=i$ (and $i\neq-1$). Similarly, $\mathsf{lev}[e][k]$
stores a pointer to the memory location of $\mathsf{lev}^{(k)}(e)$, as well as
a pointer to the memory location of the pointer to $E^{(k)}_{i}$ if
$\mathsf{lev}^{(k)}(e)=i$.

####  3.3.1 Foreground Operations

The collections $S_{i}$ and $E_{i}$ for each $i$ will be maintained in doubly
linked lists in the foreground. To access the level value $\mathsf{lev}(s)$ in
the foreground, we can enumerate all indices $k\in[0,L]$ and check the entry
$\mathsf{lev}[s][k]$ that points to $\mathsf{lev}^{(k)}(s)=i$ and list head
$S^{(l)}_{i},l\geq i$. If either $\mathsf{lev}[s][k]$ is a null pointer, or
$\mathsf{lev}[s][k]$ pointers to a value $\mathsf{lev}^{(k)}(s)=i$ but
$S_{i}^{(l)}$ is not in the foreground, then we know
$\mathsf{lev}^{(k)}(s)\neq\mathsf{lev}(s)$. Therefore, accessing the
foreground level value $\mathsf{lev}(s)$ takes time $O(L)$. Similarly,
accessing the foreground level value $\mathsf{lev}(e)$ takes time $O(L)$ as
well. We conclude that upon insertion of element $e$, enumerating all sets
$s\ni e$ to decide which set needs to cover $e$ takes time $O(f\cdot
L)=O(f\cdot\log_{\beta}(Cn))$. As can be seen in Algorithm 1 and Algorithm 2,
the runtime of other parts is constant, except for the part of feeding to a
reset, which will be analyzed in Section 3.3.3. Regarding initiating resets,
in $O(L)=O(\log_{\beta}(Cn))$ time we can go over all levels to check which
ones need to be initiated, and also check which is the highest short level, by
using $E_{i}$ which is maintained in the foreground. We remind that a short
level is a level $k$ such that $\mathsf{reset}(k)$ is not working currently in
the background, and $f\cdot\sum_{i=0}^{k}|E_{i}|<L$. Moreover, there is only
one short level reset operating per update step (the highest one).

####  3.3.2 Reset - Initialization Phase

When an instance $\mathsf{reset}(k)$ has been scheduled, it initializes its
own data structures by setting
$\mathcal{S}^{(k)}_{\mathsf{alg}}=S_{i}^{(k)}=E_{i}^{(k)}\leftarrow\emptyset,\forall
i\in[0,k+1]$, and
$\mathcal{U}^{(k)}=\mathcal{U}^{(k)+}\leftarrow\bigcup_{i=0}^{k}E_{i}$, each
maintained in a doubly-linked list. After that, enumerate all elements of
$\mathcal{U}^{(k)}$ and let $\mathcal{S}^{(k)}$ be all the sets containing at
least one element in $\mathcal{U}^{(k)}$. So
$\mathcal{S}^{(k)}\subseteq\\{s\mid-1\leq\mathsf{lev}(s)\leq k\\}$. To obtain
all the pointers to $E_{i}$, $0\leq i\leq k$, we follow the linked list
consisting of these pointers, from $E_{k}$ down to $E_{0}$. One remark is
that, during the numeration of the list from $E_{k}$ down to $E_{0}$, which
could take several update steps, some pointers might already be switched by
other resets $\mathsf{reset}(i),i<k$; we will show that this is still fine in
3.1.1. We also assign
$\mathsf{lev}^{(k)}(s)=\mathsf{lev}^{(k)}(e)\leftarrow-1,\mathsf{plev}^{(k)}(e)\leftarrow\max\\{\mathsf{plev}(e),k+1\\},\forall
e\in\mathcal{U}^{(k)},s\in\mathcal{S}^{(k)}$. For each set
$s\in\mathcal{S}^{(k)}$, store the set $s\cap\mathcal{U}^{(k)}$ as a linked
list. All the above steps will be planned in the background for the non-short
levels. If a new element $e$ is inserted by the adversary during
initialization, assign
$\mathsf{lev}^{(k)}(e)\leftarrow-1,\mathsf{plev}^{(k)}(e)\leftarrow k+1$, and
add all sets $s\notin\mathcal{S}^{(k)}$ containing $e$ to $\mathcal{S}^{(k)}$,
and enumerate $s\cap\mathcal{U}^{(k)}$; if an old element
$e\in\mathcal{U}^{(k)}$ is deleted by the adversary during the initialization,
remove it from $\mathcal{U}^{(k)}$.

Copying the memory locations of the pointers of
$\\{E_{k},E_{k-1},\cdots,E_{0}\\}$ and $\\{S_{k},S_{k-1},\cdots,S_{-1}\\}$
takes time at most $O(k)$. Obtaining the collection $\mathcal{S}^{(k)}$ and
calculating $s\cap\mathcal{U}^{(k)}$ for each set $s\in\mathcal{S}^{(k)}$
takes $O(f|\mathcal{U}^{(k)}|)$ time, so the total running time of this phase
is $O(f|\mathcal{U}^{(k)}|+k)=O(f|\mathcal{U}^{(k)}|+L)$. Since all the non-
short levels satisfy $f\cdot|\mathcal{U}^{(k)}|\geq L$, we get that the
running time of this phase for non-short levels is $O(f|\mathcal{U}^{(k)}|)$,
and for the short level reset it is $O(L)=O(\log_{\beta}(Cn))$.

####  3.3.3 Reset - Greedy Set Cover Algorithm Phase

According to the algorithm, for each element in $\mathcal{U}^{(k)}$, the
greedy set cover algorithm procedure scans the list of all the sets containing
this element at most once, and so the planned number of sets the algorithm
goes through is $O(f|\mathcal{U}^{(k)}|)$. For each such set $s^{\prime}$, we
must update $s^{\prime}\cap U$ (line $15$ in Algorithm 3), which indeed takes
$O(1)$ time, but we must store the values of $|s^{\prime}\cap U|$ for each
$s^{\prime}\in\mathcal{S}^{(k)}$ in some data structure that will allow us to
update values (line $16$ in Algorithm 3) and extract the maximum value (line
$4$ in Algorithm 3) in $O(1)$ time, if we want the reset to run in
$O(f|\mathcal{U}^{(k)}|)$ time. We shall implement this with a _truncated max-
heap_ :

######  Definition 3.3.

Let $X$ be a set of objects with key values. A _truncated_ max-heap data
structure on $X$ supports the following operations.

  * •

Removal of any object in $X$.

  * •

Change the key value of any object in $X$.

  * •

Given a threshold value $k$, return any object with maximum key value or whose
value is $\geq k$.

During the $i$th round we need to repeatedly choose sets from the max-heap
with top priority with threshold $\beta^{i}$. To implement heap operations of
the truncated max-heap in constant time, store all sets
$s\in\mathcal{S}^{(k)}\setminus\mathcal{S}^{(k)}_{\mathsf{alg}}$ in an array
of length $L$, each entry of the array is a linked list of elements in
$\mathcal{S}^{(k)}\setminus\mathcal{S}^{(k)}_{\mathsf{alg}}$. We will ensure
the following property of this array.

######  Invariant 3.2 (heap invariant).

During the $i$-round of the greedy set cover algorithm phase of
$\mathsf{reset}(k)$, for any index $0\leq j\leq i$, if $j<i$, then the $j$th
entry of the array is a linked list of sets in
$\mathcal{S}^{(k)}\setminus\mathcal{S}^{(k)}_{\mathsf{alg}}$, such that for
each of these sets $s$, we have $\lfloor\log_{\beta}(\frac{|s\cap
U|}{\mathsf{cost}(s)})\rfloor=j$; otherwise, if $j=i$, then
$\lfloor\log_{\beta}(\frac{|s\cap U|}{\mathsf{cost}(s)})\rfloor\geq j$; if
$j>i$, then the entry of the array is an empty list.

Initialization of this heap data structure takes $O(f|\mathcal{U}^{(k)}|+k)$
time. Upon insertions/deletions occurring during this initialization, we can
update the heap data structure under construction in a straightforward manner,
since we are not yet updating the levels nor building the set cover solution.
During the $i$th round of the greedy set cover algorithm phase, removal of any
object from the heap can be done in constant time by linked list operations.
If the key value $j=\lfloor\log_{\beta}(\frac{|s\cap
U|}{\mathsf{cost}(s)})\rfloor$ has changed either by the adversary or by the
background algorithm itself, we can attach it to the ($\min\\{j,i\\}$)th
linked list in the array of the heap. During the $i$th round, extraction
operation on the heap always has threshold $\beta^{i}$, so it suffices to
check if the $i$th entry of the array is empty. All of these operations take
constant time. When the $i$th round has finished, it must be the case that the
$i$th entry in the array of the heap has now become empty. So, when we enter
the $(i-1)$th round of the greedy set cover algorithm phase, 3.2 still holds.

Since we must pass through all levels from $k+1$ to $0$, we conclude that the
total running time of this phase of the reset is also
$O(f|\mathcal{U}^{(k)}|+k)=O(f|\mathcal{U}^{(k)}|+L)$. Again, for all non-
short levels this means $O(f|\mathcal{U}^{(k)}|)$, and for the short level
this means $O(L)=O(\log_{\beta}(Cn))$. We conclude that the first two phases
together of the reset (initialization and greedy set cover algorithm), run in
$O(\log_{\beta}(Cn))$ time for the short level reset. Thus, we will compute
these two phases all within a single update step, without affecting the worst-
case update time. As for the other resets, as mentioned we will compute
$O(\frac{f}{\epsilon})$ steps per update steps, thus the total number of
computations per update step will be $O(\frac{f\cdot
L}{\epsilon})=O(\frac{f\cdot\log_{\beta}(Cn)}{\epsilon})$, which is the
bottleneck.

####  3.3.4 Reset - Termination Phase

When $\mathsf{reset}(k)$ has finished and called upon to switch its memory to
the foreground, for every index $0\leq i\leq k$, we replace every pointer to
$S_{i}$ with the pointer to $S^{(k)}_{i}$, and connect all pointers to
nonempty lists $S^{(k)}_{i},0\leq i\leq k$ with a linked list.

Merging the list $S_{k+1}^{(k)}$ with the list $S_{k+1}$ on the foreground is
in fact done in the greedy set cover algorithm phase, following round $k+1$,
as it does not have worst-case runtime guarantee. Nevertheless it will be
explained here as part of the termination phase. Upon merging $S_{k+1}^{(k)}$
with $S_{k+1}$, suppose $S_{k+1}$ is equal to some $S_{k+1}^{(l)}$ for some
$l\geq k+1$; in other words, $S_{k+1}$ was computed in some instance
$\mathsf{reset}(l)$, where $l\geq k+1$. Then, for each set $s\in
S^{(k)}_{k+1}$, redirect the pointer $\mathsf{lev}[s][k]$ from the list head
$S^{(k)}_{k+1}$ to the list head $S_{k+1}^{(l)}$. After that, concatenate the
two lists $S_{k+1}^{(k)},S_{k+1}$. We can merge the two lists $E_{k+1}^{(k)}$
and $E_{k+1}$ in a similar manner. The running time of this is clearly
$O(f\cdot|\mathcal{U}^{(k)}|)$, thus not the bottleneck of the second phase.

As for the runtime of the termination phase, the number of memory pointers to
be switched is at most $O(L)=O(\log_{\beta}(Cn))$, so the worst-case runtime
is $O(L)=O(\log_{\beta}(Cn))$. For any set $s\in\mathcal{S}^{(k)}$, to access
any level value $\mathsf{lev}^{(k)}(s)$ in the background, we can follow the
pointer $\mathsf{lev}[s][k]$ and check $\mathsf{lev}^{(k)}(s)$ in constant
time; similarly we can check the value of $\mathsf{lev}^{(k)}(e)$ for any
$e\in\mathcal{U}^{(k)+}$ in constant time.

Since our data structures maintain multiple versions of the level values, and
our algorithm keeps switching memory locations between the foreground and the
background, we need to argue the consistency of the foreground data
structures; this is done in 3.1.1.

By the algorithm description, upon an element update, we scan all the levels,
and if any instance of $\mathsf{reset}(\cdot)$ has just terminated, we switch
the one $\mathsf{reset}(k)$ on the highest level $k$ to the foreground as we
have discussed in the previous paragraph, while aborting all other instances
of $\mathsf{reset}(i),i<k$. As we have seen, switching a single instance of
$\mathsf{reset}(\cdot)$ to the foreground takes $O(L)=O(\log_{\beta}(Cn))$
time, and so the worst-case time of this part is $O(L)=O(\log_{\beta}(Cn))$.
Therefore, the termination can be done in a single update step.

To conclude Section 3.3, any insertion/deletion in the foreground can be dealt
with in $O(f\cdot L)$ time, thus it can be done within a single update step.
Dealing with the short level reset (finding the highest one, initializing the
reset, and executing the greedy set cover algorithm) takes $O(L)$ time, thus
it will all be done within a single update step as well. Likewise, termination
can be done in $O(L)$ time (updating data structures of the highest finished
reset and aborting the rest). Every other $\mathsf{reset}(k)$ will take
$O(f\cdot|\mathcal{U}^{(k)}|)$ time (initialization and greedy set cover
algorithm). Since this cannot be executed within a single update step, for
each $k$ we will execute $O(\frac{f}{\epsilon})$ computations per update step.
In Section 3.4 we will prove that by working in such a pace, we can ensure
that 3.1 holds, which in turn will be enough to prove that the approximation
factor holds, by Corollary 3.1.

###  3.4 Proof of Correctness

Let us first show that our memory switching scheme preserves consistency of
the data structures on the foreground. This is nontrivial because different
foreground sets $S_{k}$ may come from different background copies
$S_{k}^{(l)}$, and they might not be compatible with each other as different
instances of $\mathsf{reset}(\cdot)$ may have different views of the data
structures.

######  Claim 3.1.1.

The foreground data structures $\\{S_{k}\\}_{-1\leq k\leq
L},\\{E_{k}\\}_{0\leq k\leq L}$ are consistent; that is, they satisfy their
specifications in Theorem 3.1.

###### Proof.

This statement is proved by an induction on time. Consider any instance of
$\mathsf{reset}(k)$. First we show that during its initialization phase,
$\mathsf{reset}(k)$ obtains a set of pointers $S_{i},E_{i},0\leq i\leq k$
which comes from a valid realization of the basic data structure defined in
Theorem 3.1. This is nontrivial because the when initialization phase scans
from $i=k,k-1,\ldots,0$, some $\mathsf{reset}(j),j<k$ could terminate and
change part of the data structures on the foreground. We will show that this
is still fine.

Recall that, during the initialization phase of $\mathsf{reset}(k)$, we have
planned a procedure that scans and copy all the pointers to lists
$S_{i},E_{i}$ where $i$ goes from $k$ down to $0$. If no
$\mathsf{reset}(j),j<k$ has switched its memory to the foreground, then in the
end, $\mathsf{reset}(k)$ can obtain a prefix of the foreground data
structures. Otherwise, suppose an instance of $\mathsf{reset}(j),j<k$ has
switched its memory to the foreground while $\mathsf{reset}(k)$ hasn’t
finished copying all the pointers.

  * •

If $j<i$ at the moment of memory switching, then since $\mathsf{reset}(j)$
only modifies levels in $[0,j+1]$, $\mathsf{reset}(k)$ will still copy a
prefix of the new version of the foreground data structures.

  * •

If $j\geq i$, then $\mathsf{reset}(k)$ will be copying the old version of
$S_{0},S_{1},\cdots,S_{i}$, which will be switched off from the foreground,
but still consistent on its own. In other words, $\mathsf{reset}(k)$ will in
the end obtain an stale version of the foreground data structure which is
still consistent with itself.

Next, let us consider the moment when $\mathsf{reset}(k)$ finishes and switch
its local memory to the foreground. As $\mathsf{reset}(k)$ was not aborted, no
other instances $\mathsf{reset}(j),j>k$ has finished; also, by the algorithm
description, any $\mathsf{reset}(j),j<k$ cannot change anything in the
foreground on levels higher than $k$. Therefore, when $\mathsf{reset}(k)$
switches, the foreground data structure is still consistent. ∎

Next, we prove that 3.1 always holds during Phase II of procedure
$\mathsf{reset}(k)$ (the greedy set cover algorithm) in the background.

######  Claim 3.1.2.

3.1 always holds.

###### Proof.

Let us prove this statement (that the two conditions of 3.1 hold) by a reverse
induction on $i$, from $i=k+1$ to 0. For the induction basis $i=k+1$, this
assumption trivially holds: For the first condition, any element deletion in
$\mathcal{U}^{(k)}$ triggers directly a removal of the element from $U$,
rather than marking it as dead; the second condition holds vacuously. Next,
consider the induction step. For the first condition, when an element in $U$
is deleted, it is removed right away from $U$, so $U$ always contains alive
elements only. For the second condition, the terminating condition of the
$i$th round implies that when the $i$th round terminates, any set
$s\in\mathcal{S}^{(k)}\setminus\mathcal{S}^{(k)}_{\mathsf{alg}}$ satisfies
$|s\cap U|/\mathsf{cost}(s)<\beta^{i}$, implying that the second condition for
round $i-1$ holds at the beginning of round $i-1$. ∎

Finally, we prove that 3.1 always holds in the foreground, which concludes the
proof of Theorem 3.1.

######  Claim 3.1.3.

3.1(1) always holds in the foreground.

###### Proof.

Consider the insertion of element $e$ in the foreground to level $j$. By the
description of the algorithm, we would have
$\mathsf{lev}(e)=\mathsf{plev}(e)=j$. Since
$\mathsf{lev}(e)=\mathsf{plev}(e)$, by definition $e$ cannot be part of
$A_{i}$ for any $i$. Thus, the insertion cannot raise $|N_{i}(s)|$ for any $i$
and $s$. Likewise, upon deletion of element $e$, we set
$\mathsf{plev}(e)\leftarrow\mathsf{lev}(e)$, thus again this deletion cannot
raise $|N_{i}(s)|$ for any $i$ and $s$.

Since insertions and deletions to the foreground cannot cause a violation to
3.1(1), the only possibility left is if 3.1(1) is violated in the background
in some system working on $\mathsf{reset}(k)$, and it is then transferred to
the foreground. Assume by contradiction that exists a set $s$ such that upon
termination of $\mathsf{reset}(k)$, we have
$\frac{|N_{j}(s)|}{\mathsf{cost}(s)}\geq\beta^{j+1}$ for some $j$.

If $j\geq k+1$, then for $|N_{j}(s)|$ to grow between right before the
initialization of $\mathsf{reset}(k)$ and right after the termination of
$\mathsf{reset}(k)$, there must exist an element $e\in s$ that joined
$N_{j}(s)$ sometime between those two time steps. For this to happen $e$ must
change its passive level, since its level cannot fall from $>j$ to $\leq j$ in
an instance of $\mathsf{reset}(k)$ where $j\geq k+1$ (because $e$ would not
participate in such a reset). This means that when $\mathsf{reset}(k)$ is
initialized, either $\mathsf{plev}(e)\leq j$ or $e$ has not been inserted yet,
and $\mathsf{plev}(e)>j$ when $\mathsf{reset}(k)$ terminates. Consider the
first case where $\mathsf{plev}(e)=i$ when the reset is initialized, where
$i\leq j$. Then by the algorithm description $\mathsf{plev}(e)$ is
$\max\\{i,k+1\\}$ when the reset terminates. But clearly
$j\geq\max\\{i,k+1\\}$ and so we reach a contradiction. Now consider the
second case where $e$ was inserted sometime during the execution of
$\mathsf{reset}(k)$. By the algorithm description $\mathsf{plev}(e)$ is $\leq
k+1$ when the reset terminates, and since $j\geq k+1$ we again reach a
contradiction.

If $j<k+1$, we claim that all elements in $N_{j}(s)$ at the termination of
$\mathsf{reset}(k)$ were in $U$ in the beginning of round $j$. Assume by
contradiction that exists an element $e\in N_{j}(s)$ when the reset
terminates, such that $e\notin U$ in the beginning of round $j$. If $e$ was
inserted during round $j$ or after, then at termination $\mathsf{plev}(e)\leq
j$ by the algorithm description, a contradiction to the fact that $e\in
N_{j}(s)$ when the reset terminates. If $e$ existed at the beginning of round
$j$, but was not in $U$ at that time, it means it has already been covered in
a previous round, meaning covered at a level $>j$, which again is a
contradiction to the fact that $e\in N_{j}(s)$ when the reset terminates. So
indeed all elements in $N_{j}(s)$ at the termination of $\mathsf{reset}(k)$
were in $U$ in the beginning of round $j$. But since we assumed by
contradiction that upon termination
$\frac{|N_{j}(s)|}{\mathsf{cost}(s)}\geq\beta^{j+1}$, we get that
$\frac{|s\cap U|}{\mathsf{cost}(s)}\geq\beta^{j+1}$ in the beginning of round
$j$, a contradiction to 3.1. ∎

######  Claim 3.1.4.

3.1(2) always holds in the foreground.

###### Proof.

It is immediate by the algorithm description that the second half of 3.1(2)
(that $\mathsf{lev}(s)=-1$ for each $s\notin\mathcal{S}_{\mathsf{alg}}$)
always holds. It remains to show that
$|\mathsf{cov}(s)|/\mathsf{cost}(s)\geq\beta^{\mathsf{lev}(s)}$, for any set
$s\in\mathcal{S}_{\mathsf{alg}}$. Since $\mathsf{cov}(s)$ can contain dead
elements as well, clearly a deletion cannot cause a violation to this
invariant, as well as an insertion. Thus the only possibility left is if
3.1(2) is violated in the background in some system working on
$\mathsf{reset}(k)$, and it is then transferred to the foreground. Assume by
contradiction that exists a set $s$ such that upon termination of
$\mathsf{reset}(k)$, we have
$|\mathsf{cov}(s)|/\mathsf{cost}(s)<\beta^{\mathsf{lev}(s)}$.

By the description of the greedy set cover algorithm, when a set $s$ joins the
partial solution $\mathcal{S}^{(k)}_{\mathsf{alg}}$ during the $i$th round, it
is guaranteed that $|\mathsf{cov}(s)|/\mathsf{cost}(s)=|s\cap
U|/\mathsf{cost}(s)\geq\beta^{i}=\beta^{\mathsf{lev}^{(k)}(s)}$; recalling
that $\mathsf{cov}(s)$ also includes dead elements, this ratio
$|\mathsf{cov}(s)|/\mathsf{cost}(s)$ may only increase later on. ∎

######  Claim 3.1.5.

Consider an instance of $\mathsf{reset}(k)$ and denote by $U_{i}$ the
collection of uncovered alive elements at the beginning of round $i$ in the
greedy set cover algorithm phase, where $i\in[0,k+1]$. Then by working at a
pace of $O(f/\epsilon)$ per update step, the reset will terminate after less
than $\frac{\epsilon}{2}|U_{i}|$ element updates following the beginning of
round $i$.

###### Proof.

Note that at the beginning of round $i$, the total number of remaining planned
computations by $\mathsf{reset}(k)$ is $O(f|U_{i}|)$, since each remaining
alive element will change its level only once, and it will take $O(f)$ time
for it to update all relevant data structures regarding this change. Each time
the adversary makes an update, the number of alive elements can increase by at
most one, so if we mark by $x$ the total number of update steps from the
beginning of round $i$ until termination, there are at most $|U_{i}|+x$
elements that we need to assign to levels, taking $O(f(|U_{i}|+x))$ time.
Notice though that $x$ is roughly $\epsilon|U_{i}|$, since the reset takes
care of $\Theta(\frac{1}{\epsilon})$ elements per update step
($\Theta(\frac{f}{\epsilon})$ computations per update step, each element
taking $\Theta(f)$ time), in which time only one can be inserted. So
$O(f(|U_{i}|+x))=O(f|U_{i}|)$, meaning the reset takes $O(f|U_{i}|)$ time for
planned and immediate steps. By working at a pace of $O(\frac{f}{\epsilon})$
computations per update step, we can finish all steps in less than
$\frac{\epsilon}{2}|U_{i}|$ update steps. ∎

######  Claim 3.1.6.

Following the termination of an instance $\mathsf{reset}(k)$, we have
$|P_{i}|<\epsilon\cdot|A_{i}|$ for all $i\leq k$.

###### Proof.

Consider the moment when the $i$th round of the greedy set cover algorithm
begins in an instance of $\mathsf{reset}(k)$ (within Phase II of
$\mathsf{reset}(k)$), where $i\in[0,k+1]$. Denote by $U_{i}$ the set of all
currently uncovered alive elements. By Claim 3.1.5, the reset will terminate
in less than $\frac{\epsilon}{2}|U_{i}|$ update steps. By the algorithm
description, each element $e\in U_{i}$ at the beginning of the $i$th round
will be assigned $\mathsf{lev}(e)$ at most $i$ in round $i$ onwards, while
$\mathsf{plev}(e)>i$. The only elements that could have level $\leq i$ with
passive level also $\leq i$, and thus belong to $P^{(k)}_{i}$, are the ones
inserted/deleted by the adversary from the $i$th round onwards. As mentioned,
there are less than $\frac{\epsilon}{2}|U_{i}|$ insertions/deletions from this
point until termination, so at the end of the reset
$|P^{(k)}_{i}|<\frac{\epsilon}{2}|U_{i}|$. Moreover,
$(|A^{(k)}_{i}|+|P^{(k)}_{i}|)$ at the end of the reset is the total number of
elements that were assigned to a level up to $i$. So eventually there will be
at least $|U_{i}|$ elements (alive and dead) covered at level $\leq i$,
meaning $(|A^{(k)}_{i}|+|P^{(k)}_{i}|)\geq|U_{i}|$ Combining this altogether
we obtain that $|P^{(k)}_{i}|<\epsilon|A^{(k)}_{i}|$ for any $\epsilon<0.5$. ∎

######  Claim 3.1.7.

When $\mathsf{reset}(k)$ terminates and is transferred to the foreground, it
does not change $A_{k^{\prime}}$, and $P_{k^{\prime}}$ can only reduce in
size, for any $k^{\prime}>k$.

###### Proof.

First, we will show that each element in $P_{k^{\prime}}$ in the foreground
before the termination of $\mathsf{reset}(k)$ remains there after the
termination. Consider such an element $e\in P_{k^{\prime}}$.
$\mathsf{plev}^{(k)}(e)\leq k^{\prime}$ upon termination, since otherwise that
would mean that $\mathsf{plev}(e)>k^{\prime}$ following $\mathsf{reset}(k)$,
and since this cannot happen due to the reset (the passive level would be at
least $k+2$), we must have had $\mathsf{plev}(e)>k^{\prime}$ in the foreground
upon termination, a contradiction to the fact that $e\in P_{k^{\prime}}$ in
that time. The only exception is if $e$ was a dead element, therefore it was
in $P_{k}$ thus in $P_{k^{\prime}}$ as well, and $e$ would be completely
removed during the reset, reducing $|P_{k^{\prime}}|$ by one.

Second, we will show that each element in $A_{k^{\prime}}$ in the foreground
before the termination of $\mathsf{reset}(k)$ remains there after the
termination. Consider such an element $e\in A_{k^{\prime}}$. Clearly
$\mathsf{lev}^{(k)}(e)\leq k^{\prime}$ upon termination, since $e$ cannot rise
to a level above $k+1$, which is $\leq k^{\prime}$. Since $e\in
A_{k^{\prime}}$, the passive level of $e$ in the foreground right before
termination of $\mathsf{reset}(k)$ is $>k^{\prime}$, thus it is also $>k+1$.
Therefore, the passive level of $e$ would not have changed due to
$\mathsf{reset}(k)$, and $e$ remains in $A_{k^{\prime}}$.

Next, we will show that no new elements join $P_{k^{\prime}}$ following the
termination of $\mathsf{reset}(k)$. Assume by contradiction that exists such
an element $e$. Either $\mathsf{lev}(e)>k^{\prime}$ or
$\mathsf{plev}(e)>k^{\prime}$ in the foreground right before the termination.
If $\mathsf{lev}(e)>k^{\prime}$, then the only way $e$ would have participated
in $\mathsf{reset}(k)$, is if before the termination of $\mathsf{reset}(k)$
there was a termination of some $\mathsf{reset}(k^{\prime\prime})$ where
$k^{\prime\prime}\geq k^{\prime}$. This would abort $\mathsf{reset}(k)$
though. Likewise, if $\mathsf{plev}(e)>k^{\prime}$ in the foreground right
before the termination, then since the passive level cannot decrease, $e$
cannot join $P_{k^{\prime}}$.

Lastly, we will show that no new elements join $A_{k^{\prime}}$ following the
termination of $\mathsf{reset}(k)$. Assume by contradiction that exists such
an element $e$. Either $\mathsf{lev}(e)>k^{\prime}$ or $\mathsf{plev}(e)\leq
k^{\prime}$ in the foreground right before the termination. If
$\mathsf{lev}(e)>k^{\prime}$, then the only way $e$ would have participated in
$\mathsf{reset}(k)$, is if before the termination of $\mathsf{reset}(k)$ there
was a termination of some $\mathsf{reset}(k^{\prime\prime})$ where
$k^{\prime\prime}\geq k^{\prime}$. This would abort $\mathsf{reset}(k)$
though. If $\mathsf{plev}(e)\leq k^{\prime}$, then since $k^{\prime}\geq k+1$,
by the algorithm description $\mathsf{plev}^{(k)}(e)$ will remain $\leq
k^{\prime}$, a contradiction, and the claim follows. ∎

######  Lemma 3.2.

3.1(3) always holds in the foreground.

###### Proof.

Assume by contradiction that there exists $k$ such that
$|P_{k}|>2\epsilon\cdot|A_{k}|$ for some $k$, at the end of update step $t$
(right before update step $t+1$). Let $t^{\prime}$ be the last time step
before $t$ that $\mathsf{reset}(k)$ was initiated. $\mathsf{reset}(k)$ was
initiated at time $t^{\prime}$ right after the termination of some
$\mathsf{reset}(k^{\prime})$, where $k^{\prime}\geq k$, by the algorithm
description. By 3.1.6, we know that at time $t^{\prime}$ (following the
termination of $\mathsf{reset}(k^{\prime})$) we have
$|P_{k}|<\epsilon\cdot|A_{k}|$ in the foreground.

Between $t^{\prime}$ and $t$, $|P_{k}|$ can rise and $A_{k}$ can change only
due to insertions/deletions, since by definition of $t^{\prime}$ no
termination of $\mathsf{reset}(k^{\prime})$ for any $k^{\prime}\geq k$ exists,
and any termination of $\mathsf{reset}(k^{\prime})$ for any $k^{\prime}<k$
would not raise $|P_{k}|$ or change $A_{k}$ by 3.1.7. By denoting $A_{k}$ at
times $t^{\prime}$ and $t$ by $A_{k}^{t^{\prime}}$ and $A_{k}^{t}$
respectively, we conclude that there must be more than
($2\epsilon\cdot|A_{k}^{t}|-\epsilon\cdot|A_{k}^{t^{\prime}}|$) update steps
between $t^{\prime}$ and $t$, since again due to one insertion/deletion only
one element can join $P_{k}$.

If we denote by $x$ the total number of update steps throughout which
$\mathsf{reset}(k)$ is executed, we get by Claim 3.1.5 that:

$x<\frac{\epsilon}{2}(|P_{k}^{t^{\prime}}|+|A_{k}^{t^{\prime}}|),$ (6)

since the collection of all elements participating in $\mathsf{reset}(k)$
initiated at time $t^{\prime}$ is $P_{k}^{t^{\prime}}\cup A_{k}^{t^{\prime}}$.
We assume that at update step $t$, $\mathsf{reset}(k)$ is still running, thus
we will reach a contradiction if:

$\frac{\epsilon}{2}(|P_{k}^{t^{\prime}}|+|A_{k}^{t^{\prime}}|)<2\epsilon\cdot|A_{k}^{t}|-\epsilon\cdot|A_{k}^{t^{\prime}}|.$
(7)

Now, notice that:

$|A_{k}^{t}|\geq|A_{k}^{t^{\prime}}|-x,$ (8)

since again, in each update step during the reset up to one element can be
removed from $A_{k}$, and we assumed that $x\geq t-t^{\prime}$. Thus, we need
to show that:

$\frac{\epsilon}{2}(|P_{k}^{t^{\prime}}|+|A_{k}^{t^{\prime}}|)<2\epsilon\cdot(|A_{k}^{t^{\prime}}|-x)-\epsilon\cdot|A_{k}^{t^{\prime}}|.$
(9)

Plugging in $x$ from Equation 6 and rearranging, we get that we need to show:

$(\frac{1}{2}+\epsilon)|P_{k}^{t^{\prime}}|<(\frac{1}{2}-\epsilon)|A_{k}^{t^{\prime}}|.$
(10)

Since we know that $|P_{k}^{t^{\prime}}|<\epsilon|A_{k}^{t^{\prime}}|$, it is
enough to show that:

$(\frac{1}{2}+\epsilon)\cdot\epsilon|A_{k}^{t^{\prime}}|<(\frac{1}{2}-\epsilon)|A_{k}^{t^{\prime}}|,$
(11)

meaning that

$2\epsilon^{2}+3\epsilon-1<0,$ (12)

which holds for any $\epsilon<\frac{1}{4}$. Thus, we reach our contradiction
and the lemma follows. ∎

We conclude that our algorithm indeed maintains 3.1, in worst-case update time
of $O(\frac{f\cdot L}{\epsilon})=O\left(\frac{f\log(Cn)}{\epsilon^{2}}\right)$
as proved in Section 3.3. Since 3.1 holds, the approximation factor of the
maintained minimum set cover is $(1+\epsilon)\ln n$, as shown in Corollary
3.1. This concludes the proof of Theorem 3.1.

##  4 Removing Dependency on Aspect Ratio

In this section we prove Theorem 1.1, by removing the dependency on the aspect
ratio $C$ in the update time.

###  4.1 Preliminaries and Basic Data Structures

As before, an element is _dead_ if it is supposed to be deleted from
$\mathcal{U}$ by the adversary, but currently resides in the system as our
algorithm has not removed it yet; an element is _alive_ if it is not dead.
$\mathcal{U}^{+}\supseteq\mathcal{U}$ is the collection of all dead and alive
elements. Define $\beta=1+\epsilon$. For each $s\in\mathcal{S}$, define the
_top level_ $\mathsf{toplev}(s)=\lceil\log_{\beta}(n/\mathsf{cost}(s))\rceil$.
Define a parameter $K=\lceil 10\log_{\beta}n\rceil$. We will partition the
hierarchy into two sequences of windows, the _even_ and the _odd_ indexed for
parameter $l$: $[lK,(l+2)K)$, and note that every even-indexed window overlaps
two odd-indexed windows, and vice versa (except the top/bottom ones); see
Figure 3 for an illustration.

######  Definition 4.1.

For any $l\geq-1$, define
$\mathcal{S}_{l}=\\{s\in\mathcal{S}\mid\mathsf{toplev}(s)\in[lK,(l+2)K)\\}$
and let $\mathcal{U}_{l}$ be the collection of all elements that the cheapest
set containing them is in $\mathcal{S}_{l}$.

######  Observation 4.1.

Each set $s\in\mathcal{S}$ is in two consecutive set collections,
$\mathcal{S}_{l}$ and $\mathcal{S}_{l+1}$, and in those two only. Each element
$e\in\mathcal{U}$ is in two consecutive element collections,
$\mathcal{U}_{l^{\prime}}$ and $\mathcal{U}_{l^{\prime}+1}$, and in those two
only.

######  Observation 4.2.

By Observation 4.1, the union of all odd-indexed element collections equals