--- title: "Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints" authors: - "Yanhui Zhu" - "Samik Basu" - "A. Pavan" doi: "10.24963/ijcai.2024/783" url: "https://ijcai.org/proceedings/2024/783" pdf: "https://ijcai.org/proceedings/2024/0783.pdf" venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence" year: 2024 pages: "7082-7090" track: "Main Track" keywords: - "Search: S: Combinatorial search and optimisation" - "Search: S: Evolutionary computation" - "Machine Learning: ML: Optimization" - "Machine Learning: ML: Evolutionary learning" --- # Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints Yanhui Zhu, Samik Basu, A. Pavan *Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 7082-7090. DOI: [10.24963/ijcai.2024/783](https://doi.org/10.24963/ijcai.2024/783) ## Abstract We present an evolutionary algorithm evo-SMC for the problem of Submodular Maximization under Cost constraints (SMC). Our algorithm achieves 1/2-approximation with a high probability 1-1/n within O(n2 K) iterations, where K denotes the maximum size of a feasible solution set with cost constraint B. To the best of our knowledge, this is the best approximation guarantee offered by evolutionary algorithms for this problem. We further refine evo-SMC and develop st-evo-SMC. This stochastic version yields a significantly faster algorithm while maintaining the approximation ratio of 1/2, with probability 1-epsilon. The required number of iterations reduces to O(nK log(1/epsilon)/p), where the user defined parameters p represents the stochasticity probability, and epsilon denotes the error threshold. Finally, the empirical evaluations carried out through extensive experimentation substantiate the efficiency and effectiveness of our proposed algorithms. Our algorithms consistently outperform existing methods, producing higher-quality solutions. ## Full text ## 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) Table 1: Approximation ratios comparison with SOTAs for Problem 1. | Algorithm | Approximation Ratio | |--------------------------------------------------------------------------------------------------|-----------------------------------| | POMC ([Qian et al., 2017]) EAMC ([Bian et al., 2020]) EVO-SMC (this work) ST-EVO-SMC (this work) | 1/2(1 - 1/e) 1/2(1 - 1/e) 1/2 1/2 | 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. Figure 1: Experimental results with various applications. ![Image](https://ijcai.org/proceedings/2024/fulltext/783/image_000000_a80c566fbd86610a37f126f19089a8ac75887cb28ac9ca0e257bd70d5fc3058e.png) 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. ## References 1. [Badanidiyuru and Vondrák, 2014] Ashwinkumar Badani- diyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1497-1514. SIAM, 2014. 2. [Bateni et al., 2019] MohammadHossein Bateni, Lin Chen, Hossein Esfandiari, Thomas Fu, Vahab Mirrokni, and Af- shin Rostamizadeh. Categorical feature compression via submodular optimization. In International Conference on Machine Learning, pages 515-523. PMLR, 2019. 3. [Bian et al., 2020] Chao Bian, Chao Feng, Chao Qian, and Yang Yu. An efficient evolutionary algorithm for subset selection with general cost constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3267-3274, 2020. 4. [Bian et al., 2021] Chao Bian, Chao Qian, Frank Neumann, and Yang Yu. Fast pareto optimization for subset selec- tion with dynamic cost constraints. In IJCAI, pages 2191- 2197, 2021. 5. [Bloom, 1970] Burton H Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422-426, 1970. 6. [Chen et al., 2022] Xuefeng Chen, Liang Feng, Xin Cao, Yifeng Zeng, and Yaqing Hou. Budgeted sequence sub- modular maximization. In Luc De Raedt, editor, Proceed- ings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 4733-4739. ijcai.org, 2022. 7. [Crawford, 2019] Victoria G. Crawford. An efficient evo- lutionary algorithm for minimum cost submodular cover. In Sarit Kraus, editor, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 1227-1233. ijcai.org, 2019. 8. [Do and Neumann, 2021] Anh Viet Do and Frank Neumann. Pareto optimization for subset selection with dynamic par- tition matroid constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12284-12292, 2021. 9. [El Halabi et al., 2022] Marwa El Halabi, Suraj Srinivas, and Simon Lacoste-Julien. Data-efficient structured pruning via submodular optimization. Advances in Neural Infor- mation Processing Systems, 35:36613-36626, 2022. 10. [Ene and Nguyen, 2019] Alina Ene and Huy L. Nguyen. A nearly-linear time algorithm for submodular maximization with a knapsack constraint. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Lan- guages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 53:1-53:12. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2019. Feldman et al., 2022] Moran Feldman, Zeev Nutov, and Elad Shoham. Practical budgeted submodular maximiza- tion. Algorithmica, pages 1-40, 2022. 11. [Friedrich and Neumann, 2015] Tobias Friedrich and Frank Neumann. Maximizing submodular functions under ma- troid constraints by evolutionary algorithms. Evolutionary computation, 23(4):543-558, 2015. 12. [Harshaw et al., 2019] Chris Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. Submodular maximiza- tion beyond non-negativity: Guarantees, fast algorithms, and applications. In International Conference on Machine Learning, pages 2634-2643. PMLR, 2019. 13. [Iyer and Bilmes, 2013] Rishabh K Iyer and Jeff A Bilmes. Submodular optimization with submodular cover and sub- modular knapsack constraints. Advances in neural infor- mation processing systems, 26, 2013. 14. [Jin et al., 2021] Tianyuan Jin, Yu Yang, Renchi Yang, Jiem- ing Shi, Keke Huang, and Xiaokui Xiao. Unconstrained submodular maximization with modular costs: Tight ap- proximation and application to profit maximization. Pro- ceedings of the VLDB Endowment, 14(10):1756-1768, 2021. 15. [Kempe et al., 2003] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a so- cial network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146, 2003. 16. [Khuller et al., 1999] Samir Khuller, Anna Moss, and Joseph Seffi Naor. The budgeted maximum coverage prob- lem. Information processing letters, 70(1):39-45, 1999. 17. [Krause and Guestrin, 2005] Andreas Krause and Carlos Guestrin. A note on the budgeted maximization of sub- modular functions. Citeseer, 2005. 18. [Kunegis, 2013] Jérôme Kunegis. Konect: the koblenz net- work collection. In Proceedings of the 22nd international conference on world wide web, pages 1343-1350, 2013. 19. [Leskovec and Mcauley, 2012] Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego net- works. Advances in neural information processing sys- tems, 25, 2012. 20. [Leskovec et al., 2007] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2-es, 2007. 21. [Li et al., 2022] Wenxin Li, Moran Feldman, Ehsan Kazemi, and Amin Karbasi. Submodular maximization in clean lin- ear time. In Advances in Neural Information Processing Systems, 2022. 22. [Li et al., 2023] Ruolin Li, Negar Mehr, and Roberto Horowitz. Submodularity of optimal sensor placement for traffic networks. Transportation Research Part B: Method- ological, 171:29-43, 2023. 23. [Mirzasoleiman et al., 2015] Baharan Mirzasoleiman, Ash- winkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Proceed- ings of the AAAI Conference on Artificial Intelligence, vol- ume 29, 2015. 24. [Nemhauser et al., 1978] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approxima- tions for maximizing submodular set functions-i. Math- ematical programming, 14(1):265-294, 1978. 25. [Padmanabhan et al., 2023] Madhavan R Padmanabhan, Yanhui Zhu, Samik Basu, and A Pavan. Maximizing submodular functions under submodular constraints. In Uncertainty in Artificial Intelligence, pages 1618-1627. PMLR, 2023. 26. [Qian et al., 2015] Chao Qian, Yang Yu, and Zhi-Hua Zhou. Subset selection by pareto optimization. Advances in neu- ral information processing systems, 28, 2015. 27. [Qian et al., 2017] Chao Qian, Jing-Cheng Shi, Yang Yu, and Ke Tang. On subset selection with general cost con- straints. In IJCAI, volume 17, pages 2613-2619, 2017. 28. [Qian, 2021] Chao Qian. Multiobjective evolutionary al- gorithms are still good: Maximizing monotone approxi- mately submodular minus modular functions. Evolution- ary Computation, 29(4):463-490, 2021. 29. [Roostapour et al., 2022] Vahid Roostapour, Aneta Neu- mann, Frank Neumann, and Tobias Friedrich. Pareto op- timization for subset selection with dynamic cost con- straints. Artificial Intelligence, 302:103597, 2022. 30. [Stelzl et al., 2005] Ulrich Stelzl, Uwe Worm, Maciej Lalowski, Christian Haenig, Felix H Brembeck, Heike Goehler, Martin Stroedicke, Martina Zenkner, Anke Schoenherr, Susanne Koeppen, et al. A human protein- protein interaction network: a resource for annotating the proteome. Cell, 122(6):957-968, 2005. 31. [Sviridenko, 2004] Maxim Sviridenko. A note on maximiz- ing a submodular set function subject to a knapsack con- straint. Operations Research Letters, 32(1):41-43, 2004. 32. [Tang et al., 2020] Jing Tang, Xueyan Tang, Andrew Lim, Kai Han, Chongshou Li, and Junsong Yuan. Revis- iting modified greedy algorithm for monotone submod- ular maximization with a knapsack constraint. CoRR, abs/2008.05391, 2020. 33. [Yaroslavtsev et al., 2020] Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin. "bring your own greedy"+ max: near-optimal 1/2-approximations for submodular knapsack. In International Conference on Artificial Intel- ligence and Statistics, pages 3263-3274. PMLR, 2020. 34. [Zheng et al., 2013] Yu Zheng, Furui Liu, and Hsun-Ping Hsieh. U-air: When urban air quality inference meets big data. In Proceedings of the 19th ACM SIGKDD interna- tional conference on Knowledge discovery and data min- ing, pages 1436-1444, 2013. 35. [Zhu et al., 2024] Yanhui Zhu, Fang Hu, Lei Hsin Kuo, and Jia Liu. Scoreh+: A high-order node proximity spectral clustering on ratios-of-eigenvectors algorithm for community detection. IEEE Transactions on Big Data, 10(3):301-312, 2024.