Engineering Algorithms for Dynamic Greedy Set Cover

The minimum set cover problem is a fundamental cornerstone of combinatorial optimization. As the canonical covering problem, it encapsulates several well-known variants, including minimum vertex cover, dominating set, and edge cover. Formally, given a universe $𝒰$ of $n$ elements and a family $ℱ$ of $m$ subsets of $𝒰$, the goal is to find a minimum-sized collection $𝒞\subseteq ℱ$ such that every element in $𝒰$ is covered by $𝒞$. The frequency $f$ of the system is the maximum number of sets that each element in $𝒰$ can be contained in. Two classic approaches define the approximation landscape for this problem: a greedy strategy yields roughly a ($\ln n$)-approximation, while a primal-dual approach achieves an $f$-approximation. These bounds are widely believed to be tight; unless $\text{P}=\text{NP}$, no algorithm can achieve a $(1-ϵ)\ln n$-approximation [24, 53], and assuming the Unique Games Conjecture, the $f$-approximation is likewise optimal [42].

Over the past decade, research on the dynamic set cover problem has expanded rapidly [1, 5, 10, 11, 12, 13, 14, 18, 32, 49, 50, 51]. In this setting, the universe $𝒰$ is modified through a sequence of update steps; in each update step, an element is either inserted into or deleted from $𝒰$. Throughout this sequence, the family of sets $ℱ$ remains static, and the universe size is bounded by $|𝒰|\le n$. Algorithms in this field are generally categorized into the low-frequency regime () and the high-frequency regime ($f\ge \ln n$). The objective is to maintain a near-optimal approximation – near $f$ or near $\ln n$, respectively – while maximizing efficiency. The most common efficiency metric is the update time, the time required to update the solution following each insertion/deletion. Additionally, there is growing research interest in the recourse [2, 4, 6, 8, 9, 17, 19, 20, 30, 31, 32, 33, 34, 45, 48, 49], which measures the number of changes made to the maintained solution per update step, a metric of increasing importance in dynamic environments where stability is required. Both metrics can be analyzed in terms of their amortized (average) or worst-case (maximum) performance.

While several works have dynamized the primal-dual approach for the low-frequency regime [1, 5, 10, 11, 12, 13, 14, 18, 32, 50, 51], this paper focuses on the high-frequency regime, where algorithms dynamize the greedy approach. Table 1 summarizes the key theoretical results for this regime, focusing only on those with low update time.

The field of dynamic algorithm engineering has seen substantial practical progress in recent years, with breakthrough results for several problems such as maximum independent set, edge orientation, and many more (see [3, 15, 16, 27, 28, 29, 35, 36, 37, 38, 39, 40] and references therein). However, while experimental results exist for other settings of the set cover problem – such as static and streaming (see [22, 26, 44, 47, 52, 54] and references therein) – the dynamic setting remains entirely unexplored empirically. This absence of practical study is a significant oversight, as the complex structures used to achieve optimal theoretical bounds often perform differently under real-world workloads. This gap persists for two primary reasons: first, the major theoretical breakthroughs only occurred within the last decade; second, and more importantly, these algorithms are inherently difficult to implement, often relying on intricate subroutines designed solely to preserve asymptotic guarantees rather than practical performance.

This work provides the first empirical study of dynamic set cover, bridging the gap between theoretical design and practical performance. We implement and evaluate four greedy-based algorithms across several real-world instances of varying scales. Our focus is on algorithms with amortized efficiency guarantees rather than worst-case bounds. This choice is motivated by practical simplicity; algorithms with worst-case guarantees often require complex “background” processes that run multiple systems simultaneously (as in [10, 50, 51]), introducing significant overhead. The algorithms presented in Table 1 consist of several intricate procedures and constraints designed solely to optimize asymptotic bounds, which can hinder practical performance. We investigate which ones provide value and which constitute bottlenecks in practice, leading us to implement the following simplified versions:

1. 1.

   The “robust” algorithm: A novel and simple algorithm based on a key property established in [50].

2. 2.

   The “local” algorithm: A simplified implementation of the algorithm from [32]. To achieve a practical approximation – avoiding the large ratio of $>1000\ln n$ – we sacrifice the theoretical $O(f\log n)$ update time in favor of better performance in practice.

3. 3.

   The “partial” algorithm: A simplification of the algorithm from [49]. We modify complex procedures intended to reduce the theoretical update time as they often increase practical update time.

4. 4.

   The “global” algorithm: A further simplified version of the amortized variant in [51]. Notably we allow $\beta \ge 1.25$, which technically weakens theoretical guarantees but is essential for significantly reducing practical update time.

Our evaluations rely on three metrics, all amortized: set cover size, update time, and recourse. Each algorithm uses a tradeoff parameter $\beta$ to balance solution quality (size) against efficiency (update time and recourse). We first evaluate the influence of $\beta$ on each algorithm individually, and then perform a comparative analysis between the four algorithms.

In Section 2, we discuss and analyze the static greedy algorithm, its implementation, and its properties, as it serves as the foundational building block for all our dynamic algorithms. Section 3 introduces the “robust” algorithm and analyzes its theoretical performance in comparison to the naive baseline which recomputes the set cover from scratch at every update step. In Section 4, we present and analyze the remaining three algorithms, highlighting how they differ from their original theoretical versions. Section 5 is dedicated to the experimental evaluation; we describe the instances used, detail our methodology, and present a discussion of our results. Finally, we conclude the paper in Section 6.

This follows immediately from Line 8 in Algorithm 1 by definition of $\mathrm{𝗅𝖾𝗏}(s)$. $◀$

Assume by contradiction that exist $s$ and $j$ such that $|N_j(s)|\ge {\beta }^j$. If $\mathrm{𝗅𝖾𝗏}(s)\ge j$, then when $s$ was added to $𝒞$, every uncovered element $e\in s$ was assigned to $\mathrm{𝖼𝗈𝗏}(s)$ and thus obeys $\mathrm{𝗅𝖾𝗏}(e)\ge j$; so $N_j(s)=\mathrm{\varnothing }$, a contradiction. If , then right after level $j$ was processed, $s$ was not in $𝒞$ and was at some level . At that time, all elements in $N_j(s)$ were uncovered by definition, so $|s\cap ℰ|\ge |N_j(s)|\ge {\beta }^j$. However, whenever $s$ is placed at a new level (lines 4 and 13), we assign it to the highest level $l^{\prime }$ such that the number of uncovered elements it contains is $\ge {\beta }^{l^{\prime }}$. Since the number of uncovered elements never increases, we cannot have $|s\cap ℰ|\ge {\beta }^j$ while $s$ remains at a level less than $j$, a contradiction. $◀$ Informally, Observation 4 shows that every set is positioned at its “correct” level, while Observation 5 implies that no set can ascend to a higher level by claiming low-level elements and increasing their levels. Essentially, all elements are positioned “as high as possible”, which captures the greedy principle in action: elements are effectively chosen at the earliest possible opportunity. As it turns out, Observations 4 and 5 suffice for the approximation analysis, and this point will be emphasized after the following approximation factor lemma.

For each element $e$ define $q_e={\beta }^{-\mathrm{𝗅𝖾𝗏}(e)}$. For each set $s\in 𝒞$, we know by Observation 4 that $|\mathrm{𝖼𝗈𝗏}(s)|\ge {\beta }^{\mathrm{𝗅𝖾𝗏}(s)}$, and thus $1\le {\sum }_{e\in \mathrm{𝖼𝗈𝗏}(s)}{q}_e$. Summing up on all sets in $𝒞$ we obtain:

Denote by $s_1,s_2,\mathrm{\dots },s_k$ the sets in an optimal set cover, and consider one of these sets $s_i$. Let $s_i=\{e_1,e_2,\mathrm{\dots },e_{x_i}\}$, where $x_i=|s_i|$. Notice that each element $e_j\in s_i$ is not necessarily in $\mathrm{𝖼𝗈𝗏}(s_i)$. Without loss of generality assume that $\mathrm{𝗅𝖾𝗏}(e_1)\ge \mathrm{𝗅𝖾𝗏}(e_2)\ge \mathrm{\dots }\ge \mathrm{𝗅𝖾𝗏}(e_{x_i})$.

Assume by contradiction that $q_{e_j}>\frac{\beta }{x_i-j+1}$ and denote $l=\mathrm{𝗅𝖾𝗏}(e_j)$. Rearranging, we get that $x_i-j+1>{\beta }^{l+1}$. Since $\mathrm{𝗅𝖾𝗏}(e_{j^{\prime }})\le l$ for any $j^{\prime }\ge j$, we know that all the $(x_i-j+1)$ elements $e_j,e_{j+1},\mathrm{\dots },e_{x_i}$ are at a level $\le l$. Since all these elements are in $s_i$, we know that $|N_{l+1}(s_i)|\ge x_i-j+1>{\beta }^{l+1}$, contradicting Observation 5. $\mathrm{⊲}$ Equipped with Claim 7, summing up on all $e\in s_i$ we get that ${\sum }_{e\in s_i}{q}_e\le \beta \cdot (1+\frac{1}{2}+\frac{1}{3}+\mathrm{\dots }+\frac{1}{x_i})\le \beta \cdot H_n\le \beta \cdot (\ln (n)+1)$, where $H_n$ is the $n$’th harmonic number. By summing up on all $k$ sets in an optimal solution, we obtain:

Since an optimal solution covers all elements, we know that:

Combining Equations 1, 2 and 3, we get that $\frac{|𝒞|}{k}\le \beta \cdot (\ln (n)+1)$, concluding the proof. $◀$ Thus, the approximation factor incurs only a slight overhead of $\beta$ compared to the classic greedy algorithm. The key insight is that this result relies solely on Observations 4 and 5. Consequently, any partition of $𝒰$ into $\mathrm{𝖼𝗈𝗏}$ sets and corresponding levels that satisfies these two observations will yield a $\beta \cdot (\ln n+1)$ approximation by including all sets with non-empty $\mathrm{𝖼𝗈𝗏}$ sets, regardless of how it was obtained. This is crucial because the dynamic algorithms presented in Section 4 maintain an element partition that satisfies a “relaxed” version of these observations. We conclude this section with the following theorem:

We evaluated our four algorithms on 120 real-world hypergraph instances. We treat the dynamic set cover problem as a dynamic vertex cover problem on hypergraphs, where dynamic hyperedges represent elements and static vertices represent sets. We started out with hundreds of static hypergraph instances [7, 23, 46]. To “dynamize” a static instance with $x$ elements, we generated a dynamic sequence of length $k=2x$, ensuring each element is inserted and deleted exactly once (staring and ending with an empty system). Insertions follow the original static ordering. We enforce a “capacity constraint” of $n=\lfloor x/10\rfloor$ active elements. While the system is below capacity, we perform an insertion with 80% probability and a deletion of one of the five most recently inserted elements with 20% probability. Once capacity $n$ is reached, we trigger a “cleanup” phase, deleting the $d$ oldest active elements, where $d\sim \text{Uniform}(1,\lfloor n/10\rfloor )$. This model specifically evaluates the performance against a mix of “fresh” deletions, “stale” deletions, and varying batch sizes. Finally, we filtered the collection to include only high-frequency instances ($f\ge \ln n$), resulting in the 120 instances used for benchmarking. See Tables 3, 4 and 5 for basic statistics of these instances.

We implemented the algorithms using C++ and compiled them using gcc 11 with full optimization (-O3 flag). The experimental evaluation was conducted on an AMD EPYC 7763 processor (64 cores, 2.45GHz) with 512MB of L3 cache and 256GB of main memory. We executed up to 32 experiments in parallel.

To reflect the “amortized nature” of the algorithms, we used three quality metrics, all amortized: set cover size, update time (processing and execution), and recourse. We measured these values for every update step of each individual experiment. The final quality metrics per experiment were calculated by averaging these values over the entire update sequence. For each of the four algorithms we chose 17 different values for $\beta$, to test the tradeoff between our quality metrics. For the smallest 115 instances (of the 120) we ran each algorithm and $\beta$ combination five times (taking an average), totaling to $115\cdot 4\cdot 17\cdot 5=39,100$ individual experiments. Due to the longer running time of the last 5 instances, we reduced the number of runs per combination and the number of different $\beta$ values per algorithm, and set a time limit of 48 hours for each individual run. Overall there were roughly $40,000$ experiments run.

We compare our algorithms using performance profiles [25]. Given a quality metric and a collection of algorithms, this plot relates for each algorithm the % of instances where it is within a $\tau$ factor of the best algorithm; the y-axis represents the % of instances and the x-axis represents $\tau$. For example, if the “partial” algorithm reaches 70% at $\tau =2.5$ in the amortized update time profile, this means that in 70% of the instances, the update time of the “partial” algorithm is within a $2.5$ factor of the best (in this case fastest) algorithm.

Since we tested 17 different values of $\beta$ for each of the four algorithms, a single visualization of all 68 variants would be cluttered. We therefore adopted a two-step analysis. In the first step, we selected six $\beta$ values per algorithm to conduct an intra-algorithm comparison of the impact of $\beta$. The performance profiles for each of these algorithms are displayed in Figure 3 (in Appendix A), and they confirm the expected correlations: $\beta$ is strongly positively correlated with the amortized set cover size and strongly negatively correlated with amortized update time and recourse across all algorithms. Furthermore, the results highlight the relative sensitivity of each metric to $\beta$; the impact is most pronounced for update time (high $\tau$ values), followed by recourse, and finally set cover size (low $\tau$ values).

Before proceeding to the second step, and to further investigate the trade-off between solution quality and computational efficiency, we provide a complementary analysis in Figure 1. Since the raw metrics vary significantly across our 120 instances, we normalize the results per instance to ensure an unbiased comparison. Specifically, for each instance and each metric separately, we identify the best-performing algorithm and $\beta$ combination. We then calculate the performance of all other combinations relative to these best-found values for each instance. Finally, we aggregate these normalized ratios across all instances using the geometric mean. Figure 1 displays the resulting quality vs. efficiency curves for the four algorithms across the full range of $\beta$ values. These curves explicitly visualize the negative correlation between solution quality and computational efficiency. Furthermore, consistent with Figure 3, they highlight the relative sensitivity of each metric to the parameter $\beta$.

In the second step, to compare the four algorithms, we selected a representative $\beta$ for each by balancing the three quality metrics. While the optimal $\beta$ is application-dependent, we defined it as the value minimizing the objective function $g(s,t,r)=s\cdot t^{1/2}\cdot r^{1/2}$, where $s,t$, and $r$ represent amortized set cover size, update time, and recourse, respectively. We chose this function to balance solution size against the other two metrics, which are strongly positively correlated. For each algorithm, we identified the $\beta$ minimizing $g$ per instance and used the median value across all instances as the “best” $\beta$. The chosen $\beta$’s were 1.99, 1.9, 1.99 and 1.495 for the robust, local, partial and global algorithms respectively. Figure 2 presents the performance profiles comparing the four algorithms using these selected values.

The global algorithm achieves the smallest average set cover in $\approx$ 95% of instances ($\tau =1$). The partial and robust algorithms follow, while the local algorithm generally yields the lowest-quality results. For amortized recourse, the hierarchy is roughly reversed: the local algorithm always performs best (100% at $\tau =1$), followed by the partial, robust, and global algorithms. Low recourse for the local algorithm is expected, as it maintains the solution by consistently “patching” it rather than triggering broader recomputations. Amortized update time reveals a more nuanced tradeoff. The local algorithm is generally the fastest, achieving the top result in $\approx$ 60% of instances. While the partial algorithm never achieves the fastest time (0% at $\tau =1$), it exhibits the steepest growth, indicating that it consistently remains near the best performance. Conversely, the robust algorithm is the fastest in one-third of instances but shows the least steep growth, failing to reach 100% even at very high $\tau$ values, suggesting significant overhead in several instances. The global algorithm’s performance lies between these two. For both efficiency metrics (update time and recourse), the $\tau$ values are significantly higher than those for the quality metric (size). This indicates that solution quality is much more stable across algorithms than efficiency, mirroring the observed influence of $\beta$ on each algorithm’s performance. To summarize, generally the local algorithm offers the highest efficiency, the global algorithm the highest quality, and the robust and partial algorithms offer a balanced middle ground. All numeric results are in Tables 3, 4, and 5.

A natural extension would be a comprehensive comparison of the four algorithms against a naive baseline that recomputes the set cover from scratch at every update. While we attempted this over several weeks by waiving the 48-hour time limit, the extreme computational overhead restricted successful runs to only the smaller instances. Preliminary results suggest that our dynamic algorithms provide drastic efficiency gains while maintaining competitive solution quality; however, full-scale benchmarking on the larger instances is required to fully verify these results.

While this study focuses on the unweighted dynamic set cover problem for its accessible and intuitive presentation, a natural next step is the weighted version. In this variant, each set has a weight and the goal is to maintain a minimum-weight cover. In practice, the weighted implementation would not differ significantly, as it would use the same core algorithmic procedures as a black box to maintain the solution.

A further compelling direction is the implementation of theoretical primal-dual-based dynamic set cover algorithms designed for the low-frequency regime (). Evaluating their performance against the greedy-based algorithms presented here across all instance types (low-frequency and high-frequency) would clarify whether primal-dual approaches are indeed superior for low-frequency instances. Furthermore, such a comparison would help identify the practical transition point where greedy algorithms become the more effective choice.