Probing transcription factor subsets in gene regulatory networks Authors: Lukas Geis, Dennis Hecker, Martin Hoefer, Ulrich Meyer, Marcel H Schulz Published: 2026 ABSTRACT AbstractTranscription factors (TFs) are essential players in the regulation of gene expression and thus have been the subject of interest in the context of diseases and the manipulation of specific cell functions or pathways. The complex interplay of TFs and genes can be modeled as a network, in which each edge represents a regulatory influence. A challenge in such networks is the identification of a set of TFs with the maximum regulatory influence, which is of particular importance in the context of perturbation studies. We model the task of finding a set of TFs to maximize the influence on a set of genes as a probing problem in a bipartite graph. We test different adaptive and non-adaptive algorithms on simulated graphs and discuss their properties and adaptivity gap. Then, we apply the algorithms on real-life data to find TFs regulating genes involved in T-cell mediated immunity and lymphoid leukemia. The approach has minimal data requirements and can be readily applied to all other types of bipartite networks.Keywords: Probing problem, Maximum coverage problem, Transcription factors, TF-gene networks Introduction Transcription factors (TFs) are regulatory proteins that influence the expression of genes by binding to the DNA in a sequence-specific fashion. TFs specifically bind accessible regions of the chromatin, which are also referred to as regulatory elements (REs) [1–3]. Due to their central role in numerous biological processes and their involvement in diseases, TFs are the subject of ongoing research. To understand the function of a TF, it is essential to know its target genes. There are various approaches to map TFs to genes, such as relying on databases that collect TF-gene interactions [4–7], correlating expression of genes and TFs across a collection of samples or single cells [8, 9], comparing changes between conditions [10, 11], observing the consequences of the perturbation of TFs [12–15], or by annotating transcription factor binding sites (TFBS) originating either from experimental data, such as ChIP-seq [16, 17], or from predictions based on known sequence binding preferences [2]. Since a gene is not only influenced by TFs binding in its immediate vicinity, all REs of a gene should be considered as locations with potential TFBS [3]. The relation between genes and TFs is often modeled via networks, in which each edge represents a regulatory influence [9, 18–21]. A challenge in such networks is the identification of TFs that regulate a gene set of interest, for example, genes of a specific pathway or disease. Commonly, the importance of TFs is assessed one at a time [22–25]. However, TFs are known to act cooperatively and pathways can be regulated by a set of TFs [1–3, 26]. A famous instance of this is the four Yamanaka factors Oct3/4, Sox2, c-Myc, and Klf4 [27]. The identification of a set of TFs in a network, either with the goal of formulating hypotheses about how a pathway is regulated or for finding potential targets for perturbation experiments, can become a combinatorial problem. For example, picking three TFs out of 400 TFs results in over 10 million possible combinations. Few works exist that explicitly aim to find sets of TFs. Gross and Blüthgen [28] intended to identify combinations of perturbations that maximize the gained knowledge about the relationships within a biological network by describing it as a maximum-flow problem. Similarly, the tool MEED suggests perturbation experiments that maximize the knowledge about regulatory relationships with a predictive logical model [29]. Wang et al. [30] built TF regulation models per gene based on perturbation data sets, which they subsequently used to define sets of perturbations which would be most informative for understanding the gene’s regulation. While these approaches promise to help in designing experiments to validate the network, they do not aim to find sets of TFs with the maximum coverage of genes in the network. We address the task of finding a set of TFs to maximize the number of target genes, i.e. the genes that are regulated by the TFs, by solving a stochastic probing problem. The probing problem asks to select a subset of elements of a given ground set that maximizes a given stochastic objective function [31–33]. Formally, for a given set A={X1,…,Xn} of n random variables and a stochastic function f:2A→R, the goal is to pick a subset S⊆A subject to some constraints such that f(S) is maximized (in expectation). Commonly, the picked subset is constrained by size [31, 32]. There are two types of algorithms for this problem. A non-adaptive algorithm decides beforehand which elements to probe, i.e. which elements to pick in S. A more general adaptive algorithm can account for realizations of recent probes when making the decision what to probe next. This makes adaptive algorithms generally stronger than non-adaptive ones, but often also substantially more complex and costly. Towards this end, it is of interest to examine the adaptivity gap, i.e., the worst-case ratio of the expected objective value of an optimal adaptive and that of a (sub-)optimal non-adaptive algorithm. In this work, we first simulate TF-gene networks as weighted bipartite graphs with varying settings and test adaptive and non-adaptive algorithms for the choice of a set of TFs (Fig. 1). We evaluate the performance of our algorithms using different objective functions, discuss their properties, and analytically bound their adaptivity gap. While an optimal solution for this task is prohibitively costly to compute, we consider efficient non-adaptive algorithms. Their results compare favorably to more costly adaptive algorithms. In other words, we propose efficient probing algorithms with near-optimal solutions that overcome the issue of testing a prohibitive number of combinations. At its core, our model is equivalent to the classical stochastic probing model [31, 34, 35], since every arbitrary objective function can also be defined in terms of a bipartite graph. However, existing work only formalizes an objective function on a set of random variables. We specialized the model to allow for a clearer and more intuitive formulation, which is especially relevant when using objective functions for which the edges are not independent. General outline of the study. Transcription factors (TFs) and their target genes are modeled as bipartite networks. Different algorithms, objective functions and graph settings are tested in simulated graphs. In an application to real data, two networks were built based on H3K27ac ChIP-seq data from T-cells. The edges between TFs and genes relied on motif-based transcription factor binding sites (TFBS), for which all predicted regulatory elements (REs) of a gene were considered [36]. The objective was to find sets of TFs with the best coverage of genes involved in T-cell mediated immunity and lymphoid leukemia In an application to real data, we construct networks for genes known to be involved in T-cell mediated immunity and genes relevant for lymphoid leukemia. Our objective is to find triplets of TFs with the best network coverage. More precisely, we want to find the combination of TFs with the highest total edge weights in the network, while each gene can only be considered for one TF. The identified TFs show specificity to the gene sets, significant co-expression within the triplets, and we can back up their relevance with literature evidence. Our approach of network construction can easily be applied to different data, since the only required data modality is a sample-specific activity measurement of REs, e.g., ATAC-seq, DNase1-seq or ChIP-seq of RE-associated histone modifications. To our knowledge, there are no other works that optimize the selection of a subset of TFs to maximize the coverage of regulated genes. Also, the probing framework can be applied to TF-gene networks derived from any other available method. In principle, it can also be used on any other kind of bipartite network, for example interactions between REs and the genes they regulate or micro RNAs and their mRNA targets. The code is available on GitHub. Methods Random graph model We consider an abstract model to express the regulator probing problem described in the introduction using a graph-theoretic approach. In our model, there is a weighted, complete bipartite graph G=(A∪B,A×B) with distinct sets of nodes A and B. We call the elements of A the regulators and the elements of B positions, respectively. We use nA:=|A| and nB:=|B| to denote their numbers. In our application on biological data, the regulators represent TFs and the positions represent genes. In general, every regulator a∈A can influence every position b∈B. The extent to which this influence arises is expressed by a strength or edge weight wa,b∈[V]={0,1,…,V} for some number V∈N. Here wa,b=0 implies that there is no influence at all. To capture uncertainty in influence, every edge (a,b)∈A×B comes with a discrete distribution Da,b over V. For simplicity, we assume the random weight wa,b is drawn independently according to Da,b. Initially, we know Da,b, but not the realization wa,b. Probing and objectives For our probing problem, we are given two integer parameters k and ℓ, with ℓ≤k≤nA. Our goal is to select a subset S⊆A of at most ℓ regulators. We evaluate the quality of this subset S by an objective function f:2A→R≥0. This function depends on the realized edge weights incident to the chosen regulators. As such, we aim to find a set S that maximizes it. We say there is a cardinality constraint of ℓ since only subsets S of at most ℓ regulators are feasible. In order to determine a good subset of regulators, we are allowed to explore or probe up to k regulators, where ℓ≤k≤nA. Upon probing a regulator a, the realized weights of all incident edges are revealed, i.e., we get to see wa,b for every b∈B. Given the k≥ℓ probed regulators, we can then select a subset S of ℓ probed regulators that is as good as possible w.r.t. f(S). Formally, we express the latter selection step within an extended definition of the objective function, which takes as argument directly the set S′ of all k probed regulators. Definition 1 For a given objective function f:2A→R≥0 with a cardinality constraint of ℓ, we define its parent-function as Consequently, our goal is to select a subset S′ of size k for probing in order to maximize f∗(S′). To model real-life gene regulatory networks, we chose a coverage function as objective function. Definition 2 The coverage function is defined by The name comes from the (weighted) MaximumCoverage problem [37, 38]: after probing a subset of regulators, we have to select a subset that maximizes the total covered weight where each position can only be covered by at most one regulator. Therefore, the selected regulators depend on each other, which is what we expect in TF-gene networks. We explore two additional objective functions fmax and fsum, which treat regulators completely independent from each other. These functions are examples of a large class of regulator additive-separable functions which we define and analyze in detail in the Supplementary Material. Definition 3 We define as functions that represent the (sum over all regulators in S of the) maximum and the sum of all incident edge weights, respectively. Policies and adaptivity gap Our probing problem can easily be cast as a finite Markov decision process [39]. Consequently, we differentiate between two classes of probing algorithms (often also called probing strategies or policies): adaptive and non-adaptive. An adaptive policy takes the k probing decisions sequentially using in each step the feedback about realized edge weights from previous steps. In contrast, a non-adaptive one decides upon the complete set S′ of k probes upfront. Note that in both cases, the final selection of ℓ elements from the set of probed elements can be made based on all realized edge weights that were observed during probing. Any adaptive policy can be described by a decision tree. Since our problem is a finite Markov decision process, there exists an optimal adaptive policy π∗. However, such a policy is usually prohibitively costly to compute. Instead, we follow the literature on probing and resort to conceptually and computationally simpler non-adaptive policies. We measure the deterioration in objective value by the standard approach of adaptivity gap. Definition 4 Let π∗ be an optimal (adaptive) policy and let π′ be an optimal non-adaptive policy for the probing problem. Suppose S∗′ and S′′ are the (random) set of k probes by π∗ and π′, respectively. The adaptivity gap is given by the ratio of the expected objective function values E[f∗(S∗′)]/E[f∗(S′′)]. For the remainder of this article, we refer to policies as algorithms. Monotonicity and submodularity The adaptivity gap in stochastic probing problems has been of significant interest over the last two decades [40–42]. In particular, monotone submodular functions f∗ are an important domain that have received significant attention. Definition 5 A non-negative set function f:2A→R≥0 is called monotone if for any two subsets S⊆T⊆A, we have f(S)≤f(T). monotone if for any two subsets S⊆T⊆A, we have f(S)≤f(T). submodular if for any two subsets S⊆T⊆A and j∈A, we have f(T∪{j})-f(T)≤f(S∪{j})-f(S), i.e., the marginal value of adding an element to a set is diminishing with the size of the set. An alternative definition of submodularity is given by f(S∪T)+f(S∩T)≤f(S)+f(T)∀S,T⊆A. submodular if for any two subsets S⊆T⊆A and j∈A, we have f(T∪{j})-f(T)≤f(S∪{j})-f(S), i.e., the marginal value of adding an element to a set is diminishing with the size of the set. An alternative definition of submodularity is given by f(S∪T)+f(S∩T)≤f(S)+f(T)∀S,T⊆A. Notably, in a seminal contribution Asadpour and Nazerzadeh [31] proved that if f∗ is monotone submodular, then the adaptivity gap is bounded by ee-1≈1.58. There are cases where this bound is tight. They also provided optimal polynomial-time non-adaptive algorithms to approximate the quality of the optimal (adaptive) algorithm up to a factor arbitrarily close to ee-1. In our probing problem, we are interested in choosing k probes to maximize the parent function f∗. Clearly, if the underlying function f is monotone, then f∗ is also monotone. In contrast to monotonicity, this inheritance is not true for submodularity. We show in the supplement that for every regulator additive-separable function fras, the parent function is submodular. In contrast, the coverage function fcov is submodular, but its parent function is not submodular. This motivates the following definition. Definition 6 A function f is parent submodular if the parent function f∗ is submodular. Greedy algorithms Our goal is to design good (non-)adaptive algorithms for regulator probing. Our approach is similar to Asadpour and Nazerzadeh [31] in the sense that we use greedy algorithms to optimize the different objective functions. We provide an overview over our algorithms, the challenges we face when applying them, and some adjustments as well as consequences for their analysis. Pseudocode of all our algorithms and new results on bounding their approximation guarantees can be found in the Supplementary Material. Asadpour and Nazerzadeh [31] analyze elementary adaptive (Amp) and non-adaptive (Namp) algorithms that myopically choose the next candidate to probe based on the set of previously chosen regulators. In Amp, the regulator chosen in step i is one to maximize the expected marginal increase in the objective function (i.e., value of the best ℓ regulators from the previously probed ones and the one in step i). Since Amp is adaptive, it can take into account the exact realizations of previous probes, but it relies on expected values for the one chosen in round i. Instead, Namp is a non-adaptive version of this algorithm, in which the expected marginal increase is computed over the entire set of all previously chosen regulators and the one in round i. For fmax∗ and fsum∗, we apply Amp without changes after a small precomputation/reduction specified in the Supplementary Material. For Namp and fsum∗ (or fmax∗), we sort regulators by expected sum (or maximum) of incident edge values and probe the k regulators with the highest expected values, respectively. This yields a simplification of the marginal increase rule in the original definition of Namp. When applying these algorithms for regulator probing with objective fcov∗, we face multiple challenges. Notably, we observe in the following that fcov∗ does not satisfy submodularity. As such, the small constant guarantees on the adaptivity gap from [31] do not readily apply. Proposition 1 fcov is monotone submodular. It is not parent submodular for k>ℓ+1. Proof Monotonicity of fcov and fcov∗ is trivial as each regulator added to a set S can only improve upon the currently obtained value by S. Now let S,T⊆A. Then, Now fix b∈B. Obviously, maxa∈Swa,b as well as maxa∈Twa,b must be greater or equal to maxa∈S∩Twa,b. Furthermore, at least one of maxa∈Swa,b and maxa∈Twa,b must be equal to maxa∈S∪Twa,b, and trivially maxa∈S∪Twa,b≥maxa∈S∩Twa,b. Hence, the last inequality holds and fcov is submodular. To prove that fcov is not parent-submodular if k>ℓ+1, consider the following instance of our problem: We have A:={1,2,3,4},B:={1,2,3,4},V:={0,1},k:=4,ℓ:=2. We have A:={1,2,3,4},B:={1,2,3,4},V:={0,1},k:=4,ℓ:=2. Every Da,b is deterministic meaning that every probability is either 1 or 0 such that we always obtain the realizations (wa,b):=1000010000101101. Every Da,b is deterministic meaning that every probability is either 1 or 0 such that we always obtain the realizations (wa,b):=1000010000101101. Consider now the subsets S⊆T⊆A,j∈A with S={1,2},T={1,2,3} and j=4. Then, Since we can scale such instances easily, for every k>ℓ+1, fcov∗ is not submodular. Moreover, as discussed above, choosing regulators to maximize fcov is a generalization of the (weighted) MaximumCoverage problem [37, 38]. The problem is NP-hard and cannot be approximated within a factor of e-1e-o(1), under standard assumptions in computational complexity. Hence, even after we have fully probed k elements (non-adaptively or adaptively), we face the problem that the optimal selection of ℓ elements is NP-hard to compute. Moreover, in each iteration of the algorithm, we need to evaluate the expected marginal increase in the optimal selection of ℓ regulators from an expanded set of probed ones. This again requires solving an instance of the same problem. An approximation ratio of e-1e for our (offline) regulator selection problem can be achieved by a generic greedy algorithm used for the maximization of submodular functions with a cardinality constraint [38]. We term this algorithm Greedy. Our algorithms rely on this procedure to estimate expected marginal gains of probing as well as to make the final selection from the set of probed regulators. More concretely, in Amp, we compute the expected increase in fcov∗ using Greedy (starting from the point where we have probed ℓ regulators). For that, we iterate over all unprobed regulators, treat them as probed by setting all their incident edge weights to their respective expected values and running Greedy on the now “uncovered” subgraph to estimate the expected marginal increase. Modifying Namp is not as simple, since the original algorithm relies on re-computations of probability distributions for each position in each iteration. We compute the expected increase precisely for the first ℓ rounds, since we know that until this point all regulators would also be selected in the optimal solution. This method, however, fails to remain efficient in subsequent steps due to computational hardness. In later rounds, we instead choose the next regulator as the one with the highest expected sum of incident edge weights. This adjustment can represent a significant departure from the structure of Namp. Unfortunately, showing general approximation factors for this (or any other simple) modification is highly non-trivial due to hardness of the underlying problem. We show approximation factors parametrized by degree in the Supplementary Material, but they significantly underestimate the observed performance in practice. In experiments, we find that the results of this algorithm compare very well against those of the adaptive variant. To emphasize our modifications, we term the modified algorithms for fcov∗ AmpCov and NampCov, respectively. For fmax and fsum, we still refer to the algorithms by Amp and Namp as we only slightly altered the non-adaptive algorithm and did not alter the adaptive algorithm at all. Finally, to accurately evaluate these algorithms for fcov in the experiments, one would also have to compute an optimal (offline) selection of regulators for the completely revealed graph. Again, this is infeasible in polynomial time. Instead, we formulate an integer program (IP) (Supp. Figure 10) that can correctly solve such an instance. Unfortunately, even a linear programming (LP) relaxation of this formulation, which can be solved in polynomial time, takes far too long for bigger instances in the Network setting (see below). The original IP itself was already infeasible for smaller instances. Thus, we use the LP-Relaxation to upper-bound the optimal offline value (and thus lower-bound the approximation ratio of our algorithms) in cases where the formulation was runtime-feasible. For other cases, we use Greedy to approximate the optimal offline value and term this application Off. Simulated graphs To explore the practicability of the algorithms discussed above, we ran the adaptive myopic algorithms (Amp/AmpCov) as well as the non-adaptive myopic algorithms (Namp/NampCov) on instances of random graphs. We focused on two scenarios: The Uniform setting: we set nA=nB=|V|=16·z for 1≤z≤20. Edge weight distributions Da,b are randomly weighted distributions produced by drawing a random weight in [0, 1] for every possible value the edge-weight can take (and then normalizing all weights). The Uniform setting: we set nA=nB=|V|=16·z for 1≤z≤20. Edge weight distributions Da,b are randomly weighted distributions produced by drawing a random weight in [0, 1] for every possible value the edge-weight can take (and then normalizing all weights). The Network setting: we set nA=16·z,nB=400·z,|V|=10 for 1≤z≤20. The edge weights model Poisson-distributed random variables with parameter λ∼[0.5,2.5]. This setting aims to model gene regulatory networks. The Network setting: we set nA=16·z,nB=400·z,|V|=10 for 1≤z≤20. The edge weights model Poisson-distributed random variables with parameter λ∼[0.5,2.5]. This setting aims to model gene regulatory networks. For each z, we generated 100 random instances of our random graph model and ran both algorithms 10 times on each graph instance for every (k,ℓ) pair with The algorithms were then evaluated with the optimal offline value OPTO that could be achieved by choosing ℓ regulators in this instance, namely an optimal offline algorithm Opt. For fcov, we used the LP-Relaxation in the (complete) Uniform setting as well as the Network setting for nA≤160. For bigger instances in the Network setting, we used the offline approximation Off. The pseudocode of the algorithms can be found in the Supplementary Material. Computational resources All algorithms and experiments were implemented in the programming language Rust. The code can be found on GitHub: https://github.com/lukasgeis/BipartiteRegulatorProbing. All experiments were run on a server with an AMD EPYC 7702P 64-Core Processor and 512GB of RAM. To speed up the experiments, instances were generated and evaluated in parallel on up to 64 threads at a time. Constructing a TF-gene network As a real-life application of the algorithms, we constructed a network consisting of TFs (regulators) and genes (positions) as nodes, with the edge weights representing the regulatory activity that a TF exerts on a gene. This regulatory activity wTF,G was estimated by taking the fraction of all REs of a gene that possess a binding site for the TF: CG are all REs of a gene, and cTF⊆CG is the subset of REs that contain a predicted binding site for the TF. We require that more REs of a gene have a TFBS than expected in comparison to all REs (p-value ≤ 0.05 in a Fisher’s exact test, Ha=greater). If this requirement is not met, wTF,G becomes zero. The contingency table for the enrichment test looks as follows: REs linked to gene GREs not linked to GREs with TFBSTFREs without TFBSTF The reasoning behind the enrichment requirement was to counteract the imbalanced number of binding sites between TFs. Otherwise, TFs with a high number of motif occurrences would have high edge weights even to genes with an average number of motif-containing REs. All edges with a non-zero edge weight are then assumed to represent a regulatory interaction between a TF and a gene. In other words, in our network a gene is expected to be regulated by all TFs that are connected with the gene. We built the network for a healthy T-cell sample (IHECRE00000187) from the International Human Epigenome Consortium (IHEC) EpiATLAS (https://ihec-epigenomes.org/epiatlas/data/, metadata version 1.1). To calculate the edge weights, two types of information were required: which REs regulate which genes, and which REs possess which TF binding sites. As candidate REs we used the peaks called on the H3K27ac ChIP-seq signal (MACS2 narrowPeak file [43]). The interactions between the candidate REs and the genes were predicted with the adapted Activity-by-Contact model [36], using the MACS2 signal value as activity and a Hi-C matrix averaged across 35 biosamples as contact data [44]. REs overlapping regions known to accumulate anomalous signal were excluded [45, 46]. The maximum distance between an RE and the transcription start site (TSS) was set to 2.5 MB and the gABC-score cutoff to 0.02. Interactions were predicted for all genes in the GENCODE v38 annotation [47]: TFBS were annotated with FIMO [48] (v.5.4.1), using a collection of non-redundant motifs from JASPAR 2022 [49], HOCOMOCO v11 [50], and the work of [51] (available under https://github.com/SchulzLab/STARE/blob/main/PWMs/2.2/Jaspar_Hocomoco_Kellis_human_transfac.txt). Only TFs which had a H3K27ac ChIP-seq peak at their promoter (±200bp around all annotated TSS) were considered (n=420). For TF dimers all constituent TFs had to have a peak at their promoter. The average base content of the REs was used as background for FIMO. For processing of genomic coordinates we used pybedtools (v0.9.0) [52, 53]. The API of MyGene.info was used for matching gene names to Ensembl IDs [54–56]. We defined two sets of genes, which are more likely to be regulated by similar TFs than the entirety of annotated genes. First, we took all genes that are known to be involved in T-cell mediated immunity from GSEA (biological process ontology GO:0002456) [57, 58]. As second gene set, we collected genes related to lymphoid leukemia by gathering all genes from DISGENET (curated v24.3) [59] that are annotated for any of the following diseases: “Leukemia, T Cell”, “human T cell leukemia”, “Early T-Cell Precursor Lymphoblastic Leukemia”, “Lymphoid Leukemias”. We were able to use only genes from the sets that we could find in the gene annotation, leaving 131 genes for T-cell mediated immunity and 83 for lymphoid leukemia. To find TFs covering the T-cell networks, we used fcov and ran 500 iterations for each k∈{30,40,50}, resulting in a total of 1,500 runs. The number of selected regulators was kept constant at ℓ=3. In other words, the goal was to find TF triplets with the best network coverage. For each run, the TF triplet with the highest return from fcov was taken. To also test other TF set sizes, we ran 10 iterations each for 3≤ℓ≤10 while setting k=50. OFF was not run for different ℓ due to its infeasible runtime for large ℓ. To measure co-expression between TFs in a triplet, the expression matrix ’genes_TPM.csv.gz’ from the IHEC EpiATLAS was taken and the correlation between genes assessed with the Pearson correlation coefficient. For each of the three possible pairs of TFs in a triplet, the correlation coefficient was calculated and then averaged to get one value per triplet. In case of TF dimers, the expression values were first averaged across the constituent TFs. Results Performance on simulated graphs Approximation factors We created multiple graph instances with varying parameters to evaluate the approximation factor of Amp/AmpCov and Namp/NampCov in the Network and Uniform setting while also varying the objective function. In the Network setting with fcov, NampCov achieved an almost equal approximation factor compared to AmpCov in all scenarios (Fig. 2). Only for k=ℓ, where we have an approximation guarantee, the adaptive algorithm slightly outperformed the non-adaptive one. The average approximation factors ranged from 0.94 to 0.99. For greater nA, we observed better approximation factors because the impact of a single regulator on the total value lessens. We also saw a clear trend where probing more and taking less yields a higher return, since we have more chances at probing great regulators without losing value for probing bad regulators. The switch from using the LP-Relaxation, which underestimates approximation factors, to the offline greedy approximation, which overestimates approximation factors, is quite visible. However, the bounds for smaller instances and the increasing trend for nA (towards the step at nA=160) suggest that regardless of instance size, our algorithms achieve at least 94% of the optimal offline value (which itself is an upper bound for the value of an optimal adaptive policy). Approximation ratios of AmpCov/NampCov in the Network setting compared to Off for fcov as a function of nA and (k,ℓ)∈14nA,24nA,34nA×14k,24k,34k,44k. The vertical line is the cutoff where Off switched from IP to Greedy The differences between algorithms were similar for the Uniform setting and the other two objective functions fmax and fsum (Supp. Figure 1+2). Compared to fcov, the approximation ratios were higher for fmax and fsum, due to the smaller value space a single edge has. Runtimes We compared the runtime of the algorithms, objective functions, and graph settings on the simulated graphs (Fig. 3, Supp. Figure 3–5). Overall, for ℓ