Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints

1 Introduction

A function f defined over a ground set V is submodular if, for any subsets S and T of V where S ⊆ T, for any x ∈ V \ T, f(S ∪ {x}) - f(S) ≥ f(T ∪ {x}) - f(T). The function f is monotone if f(T ) ≥ f(S) when S is a subset of T. Monotone submodular function optimization is a fundamental problem in combinatorial optimization, applied extensively across diverse fields such as feature compression, deep learning, sensor placement, and information diffusion, among others [Bateni et al., 2019; El Halabi et al., 2022; Li et al., 2023; Kempe et al., 2003; Zhu et al., 2024]. Over the last decade, various versions of submodular optimization problems have garnered substantial attention.

A typical monotone submodular maximization problem involves finding a set S ⊂ V such that f(S) is maximized, subject to a constraint that the set S belongs to a family of sets I known as a feasible family. An example of I is the set of all sets of size at most k, known as the cardinality constraint. Although many constrained submodular maximization problems are known to be NP-hard, several variants admit efficient approximation algorithms and have been amenable to rigorous theoretical analysis. This work specifically focuses on monotone submodular maximization under cost/knapsack constraints (SMC). Here, in addition to the monotone submodular function f, there is a modular cost function c over the ground set V . The cost function has the property that c(S) = ∑x∈S c(x). The objective of SMC is to identify a set S maximizing f(S) while ensuring that c(S) remains within a prescribed budget β. When the cost function is uniform, SMC reduces to the classical cardinality constraint submodular maximization problem. The works of [Khuller et al., 1999; Krause and Guestrin, 2005] proposed greedy algorithms for SMC that achieve an approximation ration of 12 (1 - 1/e), using O(n2 ) calls to the underlying submodular function f. The work of [Sviridenko, 2004] provided an algorithm that achieves a tight (1 - 1/e) approximation ratio for the SMC problem but has a very high time complexity of O(n5 ). Subsequent research efforts have introduced variants of the greedy algorithm aiming to improve runtime at a slight expense of the approximation quality [Feldman et al., 2022; Yaroslavtsev et al., 2020; Li et al., 2022; Ene and Nguyen, 2019; Badanidiyuru and Vondr´ak, 2014; Tang et al., 2020].

∗An extended version of this paper can be found: https://arxiv.org/pdf/2405.05942

Greedy algorithms construct solution sets iteratively by "greedily" adding one element during each iteration. This process continues as long as the underlying constraint is satisfied. While these algorithms can be rigorously analyzed, providing approximation guarantees for solution quality, they do have drawbacks. Greedy algorithms can get stuck in a local optimum. Moreover, greedy algorithms are fixed-time algorithms - meaning they can only be executed for a fixed number of iterations; even in scenarios where more computational resources (time) can be afforded, they will not produce higher-quality solutions.

Another approach to submodular optimization involves evolutionary algorithms. These algorithms mimic the population evolution procedure involving random mutations. These algorithms behave as follows. They maintain a set of feasible candidate solution sets. During each iteration, a candidate set is randomly selected for mutation. If the mutated set yields a higher-quality solution set (satisfying the constraint), then it replaces the lower-quality solution set. This approach is appealing because the random mutations can aid in moving away from the local optima. Moreover, there is no apriori bound on the number of iterations. If resources permit, the algorithm can be run for a much longer time and potentially could produce higher-quality solutions.

The work of [Qian et al., 2017] used a evolutionary algorithm framework Pareto Optimization to achieve a 12 (1 - 1/e) approximate solution to SMC. However, to guarantee this approximation ratio, the algorithm has to run exponentially many iterations. A subsequent work [Bian et al., 2020] proposed an evolutionary algorithm EAMC with improved runtime. They proved that when the algorithm EAMC is run for O(n2Kβ) iterations then the produced solution has an approximation ratio of 12 (1 - 1/e). Furthermore, empirical results of their work showed that EAMC produces solutions significantly better than those produced by greedy-based approaches. The approximation ratio of 12 (1 - 1/e) that is achieved by these evolutionary algorithms is not competitive compared with the best known (1 - 1/e) approximation ratio by the greedy algorithm (though with a much higher time complexity). Therefore, a significant objective is to design novel and efficient evolutionary algorithms that offer stronger approximation ratios.

1.1 Our Contributions

We design an evolutionary algorithm EVO-SMC that achieves an approximation ratio of 1/2. This marks a significant enhancement in the approximation guarantees for evolutionary algorithms applied to SMC. The 1/2 approximation ratio is attained when the algorithm is executed for O(n2Kβ) iterations, which is still cubic. To address this, we refine EVO-SMC and develop ST-EVO-SMC, which has a 1/2 approximation with probability 1 - ϵ and requires only O(nKβ ln (1/ϵ)/p) iterations. In this algorithm, p ∈ (0, 1] is the stochasticity probability that controls the candidate set selection. When p = 0, ST-EVO-SMC reduces to the original EVO-SMC. Algorithm ST-EVO-SMC improves the running time of EVO-SMC by a magnitude of n. Table 1 compares the approximation ratios of our algorithms with the state-ofthe-art algorithms.

To supplement the theoretical results, we conduct experiments across diverse application domains, such as influence maximization, vertex cover, and sensor placement. The empirical results demonstrate that our algorithms produce higher-quality solutions than the state-of-the-art evolutionary algorithms. The experiments also empirically demonstrate that, when allowed to run for a longer time, our algorithms perform better than the greedy-based algorithm with the same approximation ratio of 1/2. As an implementation contribution, we show that the bloom filters [Bloom, 1970] can be used in evolutionary algorithms to avoid duplicate evaluations resulting in low memory and execution times.

1.2 Additional RelatedWorks

The classical work of [Nemhauser et al., 1978] presented a greedy algorithm that achieves a (1 - 1/e) approximation ratio for the cardinality constraint problem and makes O(kn)

calls to the monotone submodular function f. The works of [Qian et al., 2015; Friedrich and Neumann, 2015] designed evolutionary algorithms for this problem using the Pareto Optimization framework while achieving the same approximation guarantee of (1 - 1/e). The subsequent work of [Crawford, 2019] designed evolutionary algorithms that significantly reduced the runtime while achieving an approximation ratio of (1 - 1/e - ϵ). For the dynamic cost constraints, Pareto Optimization [Roostapour et al., 2022] and its variant [Bian et al., 2021] are proven to admit 1/2(1 - 1/e) approximation. The works in [Iyer and Bilmes, 2013; Padmanabhan et al., 2023] considered the scenario where the function c is also submodular. A related problem to SMC is maximizing f - c, which has been studied in [Harshaw et al., 2019; Jin et al., 2021; Qian, 2021]. Evolutionary algorithms have been proposed for a few other variants of submodular optimization problems [Chen et al., 2022; Do and Neumann, 2021].

2 Preliminaries

Given a ground set V of size n and a set function f : 2V → R, f is monotone if for any subsets S ⊆ T ⊆ V , f(T) ≥ f(S). The marginal gain of adding an element x ∈ V \ S into S is f({x} | S) ≜ f(S ∪ {x}) - f(S). We write f({x} | S) = f(x | S) for for brevity and assume that f is normalized, i.e., f(∅) = 0. A function f is submodular if for any set S ⊆ T ⊆ V and any element x ∈ V \ T, the marginal gain of the function value of adding x to S is at least the marginal gain in the function value of adding x to a larger set T. This property is referred to as diminishing return. Formally,

We consider a modular cost function c : 2V → R over a set S ⊆ V where c(S) = ∑s∈S c(s). Note that a function is modular iff the equality of Eq. (1) holds. The density of an element e adding to set S is defined to be f(e|S) c(e) . Define the maximal size of a feasible set as Kβ = max{|X| : X ⊆ V ∧ c(X) ≤ β}.

Problem 1 (Submodular Maximization with Cost constraints (SMC)). Given a monotone submodular function f : 2V → R and a modular cost function c : 2V → R, a budget β, find a subset X ⊂ V such that argmaxX⊂V,c(X)≤β f(X).

The Chernoff bound is an exponentially decreasing upper bound on the tail of random variables. We present the form of the definition that will be used in this paper.

Lemma 1 (Chernoff Bound). Consider independent 0-1 variables Y1, · · · , YT with the same expectations (means) and

Oracles. In this paper, our algorithms are designed under the value oracle model, which is based on the assumption that there exists an oracle capable of returning the value f(S) with a set S. The specific value of f(S) can be the expected influence spread in influence diffusion [Kempe et al., 2003], the covered vertices in directed vertex coverage, or entropy in sensor placement. Our computational complexity analyses and experiments are based on oracles.

3 An Evolutionary Algorithm EVO-SMC

In this section, we introduce an evolutionary algorithm EVOSMC for Problem 1 along with its theoretical guarantee and analysis. We proceed with defining an auxiliary function g, referred to as surrogate function in [Bian et al., 2020] that is useful in this algorithm.

Definition 1 (Surrogate function g(X)). For a set X ⊆ V ,

The pseudocode of EVO-SMC is presented in Algorithm 1. The algorithm maintains three sets of candidate solutions F,G,G′ . The i-th element of each F and G is of size i, and are denoted by Fi and Gi. G′i is an augmentation of set Gi using a maximal marginal gain element (inspired by [Yaroslavtsev et al., 2020]). The candidate solutions conform to the cost constraint for the problem. The algorithm takes an input T, the loop controlling parameter describing the number of iterations, and outputs the set for which the valuation of the objective function f is maximal.

At every iteration, the algorithm randomly selects a set S from the candidate solution sets F and G and "mutate" S (lines 3-4). The MUTATE procedure uniformly at random flips the membership of the elements in S with probability 1/n. More specifically, for every element in V , if it appears in S, remove it from S with probability 1/n, otherwise add it to S with probability 1/n. If the mutated set S′ satisfies the budget constraint, the algorithm compares S′ with a set in the solution pools F and G with the same size as S′ . The corresponding set(s) in the solution pools will be updated if S′ is better w.r.t. g value or f value. The algorithm also considers an augmented solution G′ with the largest marginal gain (lines 11-14), which will be necessary for the theoretical analysis.

Theorem 1. Given a monotone submodular set function f, a modular cost function c, a cost constraint β, let OPTβ = argmax{f(X) | X ⊆ V, c(X) ≤ β}. If Kβ = max{|X| | X ⊆ V ∧ c(X) ≤ β}, then after T ≥ max{4en2Kβ, 16en2 logn} iterations, Algorithm 1 outputs X such that with probability 1 - 1n ,

Algorithm 1: EVO-SMC

Input : f : 2V →R+, c : 2V →R+, total number of iterations T ∈ Z>0, cost constraint β ∈ R>0 Output: argmaxX∈{F0,··· ,Fn-1,G0,··· ,Gn-1,G′0 ,··· ,G′n-1 } f(X) 1 Fj ← ∅,Gj ← ∅,G′j ← ∅ for all j ∈ [0, n-1] 2 for t ← 1 to T do 3 S ←Random({F0, · · · , Fn-1,G0, · · · ,Gn-1}) 4 S′ ←MUTATE (S) 5 i ← |S′ | 6 if c(S′ ) ≤ β then 7 if f(Fi) < f(S′ ) then 8 Fi ← S′ 9 end 10 if g(Gi) < g(S′ ) then 11 Q ← Gi ∪ {v} s.t. v = argmax e∈V \Gi ,c(e)≤β-c(Gi ) f(e | Gi) 12 if f(Q) > f(G′i) then 13 G′i ← Q 14 end 15 Gi ← S′ 16 end 17 end 18 end

In order to prove the above theorem, we will introduce an auxiliary variable ω, which keeps track of a good mutation. We proceed with the definition of ω and followed by a necessary lemma for the proof of Theorem 1.

Definition 2 (Good mutation and ω). The valuation of ω at the end of iteration t is denoted by ω(t). We say that ω(0) = 0, i.e., ω initially is 0. ω(t) = ω(t - 1) + 1 is incremented iff the following two conditions are met during an iteration t

1. A specific set S = Gω(t-1) is selected for mutation at line 3 of Algorithm 1.
2. There is exactly one element added to S during MUTATE procedure, nothing else, say S′ = S ∪ {a}, where a = argmaxe∈OPTβ\(S∪{o∗ }) f (e|S) c(e) , where o∗ = argmaxe∈OPTβ c(e).

The above conditions collectively correspond to a good mutation. In other words, the valuation of ω is incremented at the end of iteration t iff a good mutation occurs.

At the end of iteration t, we define Xt to be the set where Xt = Gω(t). Note that, if for iterations i and j such that ω(i) = ω(j) and i > j, then f(Xi) ≥ f(Xj) and g(Xi) ≥ g(Xj), which are guaranteed by lines 7-14 of Algorithm 1.

Next, we present the lemma that forms the basis for the proof of the Theorem 1.

Lemma 2. In Algorithm 1, at the beginning of an iteration t, if the set S is selected for mutation such that c(S) ≤ c(OPTβ) - c(o∗ ) where o∗ = arg maxe∈OPTβ c(e), and if the algorithm adds the element v to S where v =

arg maxe∈OPTβ \(S∪{o∗ })

Proof. Since v = argmaxe∈OPTβ\(S∪{o∗ }) f (e|S) c(e) , for every u ∈ OPTβ \ (S ∪ {o∗ }), we have

Next consider the following inequalities.

Rearranging the terms concludes the proof of Lemma 2.

To finish the approximation guarantee proof of Theorem 1, we next prove the following lemma.

Lemma 3. For any iteration t ∈ [1, T ], let Xt be the set with size ω(t) at the end of iteration t, then we have:

Proof. We prove this lemma by regular induction.

Base Case: For the first iteration t = 1 of Algorithm 1, we have two cases B-1 and B-2.

Case B-1: ω is not incremented, then we have ω(1) = ω(0) = 0. By the definition of Xt, |X0| = |X1| = ω(1) = 0 and X1 = ∅. So X1 holds for Lemma 3 by the following inequality.

Case B-2: ω is incremented, then we have ω(1) = ω(0) + 1 = 1. Since this is the first iteration, X0 = ∅, |X1| = 1. Assume that the element in condition 2 of Definition 2 is v. Then, X1 = {v}, and by applying Lemma 2, we have

If f({o∗ }) ≥ 12 f(OPTβ), then as per the lines 11-14 of Algorithm 1, it is guaranteed to admit a 1/2 approximation. Therefore, we focus on the case where f({o∗ }) < 12 f(OPTβ). Using this relation, we have

Thus, Lemma 3 holds for the base case (t = 1). Next, we prove that for iterations t ∈ (1, T ], Lemma 3 still holds.

Induction Steps: For iterations t > 1, the induction hypothesis (I.H.) is: at the end of iteration t - 1, we have

For every iteration t > 1, we analyze Xt. We also have two cases I-1 and I-2 based on whether ω is incremented.

Case I-1: If ω is not incremented, then we have ω(t) = ω(t - 1), and |Xt| = |Xt-1| = ω(t -1). Furthermore, the Algorithm 1 (lines 7-14) ensures that g(Xt) ≥ g(Xt-1). Therefore, by Definition 1, we can derive

Rearranging the above inequality, we have

This concludes the proof of Lemma 3 for Case I-1.

Case I-2: If ω is incremented, then we have ω(t) = ω(t - 1) + 1. In this case, Xt-1 is selected for mutation and the good mutation results in |Xt| = |Xt-1 ∪ {v}| where v = arg maxu∈OPTβ \(Xt-1∪{o∗ }){ f (u|Xt-1) c(u) }.

We argue that, in this case, the algorithm already has admitted a 1/2-approximation at the end of iteration t - 1.

We proceed with the following claim which can be proved by considering the cases of o∗ ∈ Xt-1 and o∗ /∈ Xt-1.

Claim 1. WLOG, for any iteration t < T, when c(Xt-1) < c(OPTβ) - c(o∗ ) we claim that

Otherwise, at the end of iteration t - 1, the algorithm has already admitted a 1/2-approximation.

Going back to the proof for Case I-2 of the Lemma 3, as per its condition: c(Xt-1) < c(OPTβ) - c(o∗ ). By rearranging Lemma 2 with S = Xt-1, we have:

Now observe that for a specific cardinality of the parameter, the function g(·) is non-decreasing. Therefore,

Thus, using the above inequalities, we have:

This concludes the proof for Lemma 3.

Justification for 1/2 - approximation. If at the end of some iteration t′ , c(Xt′) ≥ c(OPTβ) - c(o∗ ), then by Lemma 3, EVO-SMC admits 1/2 - approximation.

If there does not exist such t′ , we consider the last iteration t where ω is incremented. Similar to the proof of Case I-2 in Lemma 3, we analyze c(Xt-1 ∪ {v}). Note that, ω is incremented for a good mutation where v = arg maxe∈OPTβ \(Xt-1∪{o∗ }){ f (e|Xt-1) c(e) }. In that case, we can claim c(Xt-1 ∪ {v}) ≤ β, which follows from

(Recall that o∗ is the element in OPTβ with the maximal cost.)

After such a good mutation, if c(Xt-1 ∪ {v}) ≥ c(OPTβ) - c(o∗ ), then the algorithm will output the optimal solution. The reason is that ω(t) can be up to n, i.e., the potential solution set size |Xt| = |Xt-1 ∪ {v}| can be as large as n. Otherwise, the algorithm can keep running until c(Xt-1 ∪ {v}) ≥ c(OPTβ) - c(o∗ ).

Bound on the Number of Iterations. We analyze the running time of Algorithm 1 when it achieves a 1/2 approximation. The following Observation 1 bounds the probability of a good mutation and Lemma 4 concludes the analysis.

Observation 1. ω is incremented with a probability at least 1 2en2 at the end of every iteration.

Lemma 4. In Algorithm 1, define variable Yi for iteration i ∈ [1, T ] where Yi = 1 if ω(i) = ω(i - 1) + 1 and Yi = 0 otherwise. If T ≥max{4en2Kβ, 16en2 logn}, then

Proof. Observation 1 lower bounds the probability of Yi = 1 for an iteration i. Thus, µ = E[Y ] = E [∑Ti=1 Yi ] = Tρ ≥ T · 1

2en2 . We can apply Chernoff bound as presented in Lemma 1 to claim the following inequalities.

The first inequality holds if we take T ≥ 4en2Kβ. The second inequality follows from the Chernoff bound with η = 1/2. The last inequality holds because T ≥ 16en2 log n.

Lemmas 3 and 4 conclude the proof of Theorem 1.

4 Stochastic Evolutionary Algorithm ST-EVO-SMC

In this section, we correlate the idea of biased technique from [Crawford, 2019] and design a faster algorithm ST-EVOSMC for Problem 1.

The algorithm (Algorithm 2) has input parameters ϵ ∈ (0, 1] and p ∈ (0, 1] to allow users to balance the approximation guarantee and running time. The larger ϵ is, the lower the approximation the algorithm admits, and fewer iterations are required. One can notice that ST-EVO-SMC is deducted to Algorithm 1 if p = 0. On the other hand, if p is very large, the algorithm becomes a sampling-based stochastic algorithm similar to [Mirzasoleiman et al., 2015]. The given parameter p controls the stochasticity probability of finding a "good" candidate set in the first condition of Definition 2. In Algorithm 1, the probability of randomly selecting a set for mutation is 1 2n . However, in ST-EVO-SMC, the probability is at least p. Therefore, Algorithm 2 can grow ω rapidly and results in smaller amount of iterations.

Theorem 2. With a monotone submodular function f, modular cost function c, cost constraint β, the maximal seed set size Kβ, error threshold ϵ ∈ (0, 1] and stochasticity probability p ∈ (0, 1], let OPTβ = argmaxX⊆V,c(X)≤β{f(X)}. After T ≥ 2enKβ ln (1/ϵ)/p iterations, Algorithm 2 outputs X and admits 1 2 - approximation with probability 1 - ϵ.

Proof Sketch: The idea is to bond the increment of ω (line 9) with a good mutation. If ω is incremented, then Gω at line 6 has been selected for mutation for at least H time, and it is very likely that there ever exists at least one good mutation during those mutations. If we define Et: ω was incremented at the end of iteration t; Ft: Given Et, there exists at least one good mutation during some iteration(s) since the last iteration ω was incremented. We have Claim 2 showing that Ft happens with probability 1 - ϵ given that Et happens.

Algorithm 2: ST-EVO-SMC

Input : f : 2V →R+, c : 2V →R+ T ∈ Z>0, β ∈ R>0, ϵ ∈ (0, 1], p ∈ [0, 1] Output: argmaxX∈{F0,··· ,Fn-1,G0,··· ,Gn-1,G′0 ,··· ,G′n-1 } f(X) 1 Fj ← ∅,Gj ← ∅,G′j ← ∅, for all j ∈ [0, n-1] 2 ω ← 0, ℓ ← 1,H ← ⌈en log (1/ϵ)⌉ 3 for t ← 1 to T do 4 S ←Random({F0, · · · , Fn-1,G0, · · · ,Gn-1}) 5 if FLIP-COIN(p) = heads then 6 S ← Gω 7 ℓ ← ℓ + 1 8 if ℓ % H = 0 then 9 ω ← ω + 1 10 end 11 end 12 S′ ←MUTATE (S) 13 i ← |S′ | 14 if c(S′ ) ≤ β then 15 if f(Fi) < f(S′ ) then 16 Fi ← S′ 17 end 18 if g(Gi) < g(S′ ) then 19 Q ← Gi ∪ {v} s.t. v = argmax e∈V \Gi ,c(e)≤β-c(Gi ) f(e | Gi) 20 if f(Q) > f(G′i) then 21 G′i ← Q 22 end 23 Gi ← S′ 24 end 25 end 26 end

Analogous to the proof of Theorem 1, we need the following lemma to guarantee a 1/2-approximation ratio.

Lemma 5. For every iteration t such that 1 ≤ t ≤ T, let Xt be the set with size ω(t) at the end of iteration t, then with probability 1 - ϵ, we have:

Proof Sketch: The proof uses strong induction proof methods. The base cases include iterations with ω = 0 at time and the first iteration with ω = 1. Conditioned on ¬Et, Lemma 3 can be verified; when Ft occurs, applying Lemma 2 will finish the proof. For inductive steps, the inductive hypothesis is: Eq. (6) is true for all iterations i such that 1 ≤ i < t. The proof follows similar to Case I-2 proof in Section 3.

The following lemma ensures that ω has been incremented for Kβ times after T iterations with probability 1 - ϵ.

Lemma 6. In Algorithm 2, define 0 - 1 variables Yi for iteration i ∈ [1, T] where T ≥ 2enKβ ln (1/ϵ)/p. Yi = 1 if ℓ is incremented at line 7 of Algorithm 2, 0 otherwise. Then,

5 Experiments

EVO-SMC and ST-EVO-SMC are evaluated on influence maximization, directed vertex cover, and sensor placement with costs. We compare our algorithms with the evolutionary EAMC [Bian et al., 2020] and the deterministic algorithm Greedy+Max [Yaroslavtsev et al., 2020] (1/2-approximation and runs in O(nKβ)). We implement our algorithms and baselines in C++ (https://github.com/yz24/evo-SMC). We run our algorithms and EAMC 20 times and report the medians.

Implementation Accelerations. The mutation procedures in algorithms EVO-SMC, ST-EVO-SMC and EAMC are performed independently at every iteration. Therefore, the set after mutation S′ can stay the same with non-trivial probability or be equal to some set that has already been considered. Thus, to avoid repeated evaluations of the objective f and g over the same set, we maintain a bloom filter [Bloom, 1970] and pre-check the incoming set S′ . In our implementations and results, the number of evaluations of f is incremented only if an evaluation of f(S′ ) is actually performed.

5.1 Applications and Experimental Settings

Influence Maximization with Costs. Influence maximization in a social network G = (V,E) seeks to maximize E[IC(X)], the expected number of influenced users influenced by the propagation of information from a subset of users (seed set) X ⊆ V . The Independent Cascade (IC) model estimates E[IC(X)] with propagation probabilities p(u, v) [Kempe et al., 2003]. In real-life scenarios, there is a total budget β, and each node v ∈ V has a cost c(v) (can be viewed as an incentive) in the propagation process. Hence, the cost-constrained influence maximization problem can be formulated as: finding X such that argmaxX⊆V,c(X)≤β E[IC(X)]. We define a linear cost function c : V → R+ proportional to the out-degree out(v) [Jin et al., 2021], where c(v) = λ · out(v)γ with free parameters γ and λ. If out(v) = 0, c(v) is set to 1. In our experiments, we use Facebook [Leskovec and Mcauley, 2012] and Film-Trust networks [Kunegis, 2013]. We run the algorithms with fixed budget β = 20 and generate node costs with λ = 1.2, γ = 1.5.

Directed Vertex Cover with Costs. Let G = (V,E) be a directed graph and w : 2V → R≥0 be a modular weight function on a subset of vertices. For a vertex set S ⊆ V , let N(S) denote the set of vertices which are pointed to by S, formally, N(S) = {v ∈ V | (u, v) ∈ E ∧ u ∈ S}. The weighted directed vertex cover function is f(S) = ∑u∈N(S)∪S w(u), which is monotone submodular. We also assume that each vertex v ∈ V has an associated non-negative modular cost function c(v) [Harshaw et al., 2019] defined by c(v) = 1 + max{d(v) - q, 0}, where d(v) is the out-degree of vertex v and the non-negative integer q is the cost penalty. The objective of this task is to find a subset S such that argmaxS⊆V,c(S)≤β ∑u∈N(S)∪S w(u). We use Protein network [Stelzl et al., 2005] and Eu-Email network [Leskovec et al., 2007] in this application. We assign each node a weight of 1 and generate costs as mentioned above. We report results of β = 30 and cost penalty q = 5 for both networks.

Sensor Placement with Costs. We use a real-world air quality data (light and temperature measures) [Zheng et al., 2013] [Bian et al., 2020] collected from 36 monitoring stations in Beijing. We calculate the entropy of a sensor placement using the observed frequency. Each sensor is assigned a positive cost from the normal distribution N (0, 1). We maximize the submodular Entropy function with a budget β = 10.

5.2 Results

The comparison results on influence maximization (FilmTrust and Facebook), vertex cover (Protein and Eu-Email) and sensor placement (Beijing) are illustrated in Figures 1(a), 1(b), Figures 1(c), 1(d) and Figures 1(e), 1(f), respectively. Note that the objective values and runtime are normalized by the objective value and number of oracle calls made (O(nKβ)) by the Greedy+Max algorithm. The grey lines in the figures are 1's, corresponding to the objective value and oracle evaluations of Greedy+Max.

Due to the accelerations with bloom filters and pre-check step, our algorithm EVO-SMC is as efficient as EAMC. Moreover, the stochastic version algorithm ST-EVO-SMC consistently performs better than EAMC and outperforms Greedy+Max after making approximately two times oracle evaluations of Greedy+Max (exceeding the grey horizontal lines). As expected, the objective values of EVO-SMC

grow slowly compared to ST-EVO-SMC. The reason is that EVO-SMC randomly selects a set to mutate while ST-EVOSMC performs the selection process with a purpose (with a stochasticity probability p). We can also observe that when ϵ = 0.1, ST-EVO-SMC produces higher-quality results than with larger error thresholds, which is consistent with the theoretical guarantees. In Figure 1(e), we plot the results with various p choices. With a larger p = 0.5, ST-EVO-SMC has a faster initial increase compared with ST-EVO-SMC(p = 0.2).

During the experiments, we observe that the valuation of cost of partial solutions accumulates to β quickly and then stay close to β. This means there were a very small portion or no elements to evaluate to find the augmented element (line 19 of Algorithm 2), which is a reason why EVO-SMC is as efficient as EAMC.

6 Conclusions

In this paper, we proposed novel evolutionary frameworks for submodular maximization with cost constraints. Our algorithms achieve competitive approximation guarantees compared to the state-of-the-art evolutionary methods. Empirical studies demonstrate that our algorithms are also efficient. Future work would be designing faster algorithms that can efficiently adapt to the dynamic cost constraint settings. Unlike EAMC [Bian et al., 2020], the surrogate function defined in our paper is independent of the budget β. Therefore, it is promising to investigate how our framework can deal with budget changes in dynamic cost settings.

Acknowledgements

Part of Pavan's work is supported by NSF grant 2130536.