An Efficient Evolutionary Algorithm for Minimum Cost Submodular Cover

1 Introduction

A function f : 2S → R≥0 defined on subsets of a ground set S is monotone submodular if it possesses the following two properties:

1. For all A ⊆ B ⊆ S, f(A) ≤ f(B) (monotonicity).

Monotone submodular set functions and optimization problems are found in many applications in machine learning and data mining. In this paper, the NP-hard Minimum Cost Submodular Cover Problem (MCSC) is considered, which is defined as follows.

Problem1 (MinimumCost Submodular Cover (MCSC)). Let S be a ground set of size n. Let c : 2S → R≥0 be a modular 1 function such that c(X) = 0 if and only if X = ∅, and f : 2S → R≥0 be monotone submodular. Given a threshold τ ≤ f(S), MCSC is to find argmin{c(X) : X ⊆ S, f(X) ≥ τ}. The function c is called the cost, while f is called the benefit.

1 The function c is modular if c(X) = ∑x∈X c({x}) for all X ⊆ S.

Applications of MCSC include data summarization [Mirzasoleiman et al., 2015; 2016], active set selection [Norouzi-Fard et al., 2016], recommendation systems [Guillory and Bilmes, 2011], and viral marketing in social networks [Kuhnle et al., 2017].

The standard greedy algorithm 2 is an effective, efficient approximation algorithm for MCSC [Wolsey, 1982]; however, once the greedy solution has been obtained, it is unclear how it could be improved if more computational resources are available. Therefore, it is of interest to employ methods that can improve the solution quality at the expense of more runtime, while maintaining a worst-case guarantee. For this reason, an evolutionary algorithm has recently been proposed for MCSC [Qian et al., 2015a].

Although random search methods such as evolutionary algorithms (EA) can find better quality solutions in practice, it is difficult to analyze the approximation quality of evolutionary algorithms. The algorithm of Qian et al. is able to improve upon the greedy solution in practice, but requires expected exponential time 3 to have a worst-case guarantee similar to that of the greedy algorithm. Furthermore, no evolutionary algorithm exists in prior literature for MCSC that achieves such an approximation ratio in polynomial time.

1.1 Contributions

This paper presents the novel algorithm, EASC (Evolutionary Algorithm for Submodular Cover, Alg. 1), which is the first polynomial-time evolutionary algorithm for MCSC with constant, bicriteria approximation ratio: EASC finds a solution A such that f(A) ≥ (1 - ϵ)τ and c(A) ≤ (ln(1/ϵ) + 1)c(A∗ ), where A∗ is an optimum solution and ϵ ∈ (0, 1) is an input parameter. The expected time is O(n3 ((cmax/cmin) ln(1/ϵ))2 ), where cmax and cmin are the maximum and minimum cost of a single element s ∈ S, respectively. If cmax/cmin is bounded by a polynomial in n and ϵ is a constant, then EASC finds a near-feasible solution to MCSC with a constant approximation ratio in expected polynomial time.

In contrast to existing EAs that have been analyzed for submodular optimization problems [Qian et al., 2015b; 2015a;

2 The greedy algorithm is discussed in the Appendix in the full version of the paper.

3 Time is measured in number of evaluations of f and c, as is commonly done [Badanidiyuru and Vondr´ak, 2014].

2017], EASC is not a generic EA for multi-objective optimization. Instead, EASC takes advantage of the structure of monotone submodular functions to quickly strengthen its population. A key idea in EASC is that the range [0, τ] is discretized into bins and subsets of X ⊆ S are mapped to bins based on the value of f(X). Solutions within a bin compete with one another using a novel measure of cost-effectiveness. Both the bin structure and notion of cost-effectiveness are designed to take advantage of monotonicity and submodularity. It is likely that these ideas have potential to be applied to monotone submodular optimization problems other than MCSC.

EASC is experimentally evaluated on instances of the Influence Threshold Problem (IT) [Goyal et al., 2013; Kuhnle et al., 2017] on real social network datasets. EASC is compared to both the greedy algorithm as well as the existing EA that has been analyzed for MCSC, POM [Qian et al., 2015a]. Both EASC and POM are able to find better solutions than the greedy algorithm on the problem instances, which demonstrates the value of EAs for MCSC. In addition, EASC is shown to converge faster than POM on some instances.

Organization. Related work is first discussed in Section 1.2. Then, EASC is described in detail in Section 2. Theoretical results on the approximation ratio of EASC are presented in Section 3. Finally, the application and an experimental analysis of EASC is given in Section 4.

Notation. The following notation will be used throughout the paper. For x ∈ S, define c(x) = c({x}) and f(x) = f({x}). Define cmin = minx∈S c(x), and cmax = maxx∈S c(x). Let fτ(X) = min{f(X), τ} for all X ⊆ S. The notation for marginal gain is shortened to ∆f(X, x) = f(X ∪ {x}) - f(X) for X ⊆ S and x ∈ S. Finally, exp(a) denotes the exponential function a ↦→ ea .

1.2 RelatedWork

Evolutionary algorithms (EAs) have previously been analyzed for submodular optimization problems [Friedrich and Neumann, 2015; Qian et al., 2015a; 2015b; 2017; Friedrich et al., 2018]. In general, these EAs work by maintaining a population of non-dominating 4 solutions. Iteratively, a random solution from the population is selected and mutated. If the new solution is not strictly dominated by an existing solution in the population, it is kept 5 in the population and solutions dominated by the new solution are removed from the population. These EAs are quite generic and apply broadly to multi-objective optimization problems. In contrast, EASC is designed specifically for MCSC.

Friedrich and Neumann (2014) and Qian et al. (2015b) analyzed similar EAs for the problem of maximizing a monotone, submodular function with respect to a cardinality constraint k. Friedrich and Neumann obtained as good an approximation ratio as the greedy algorithm in expected O(n2 (log(n) + k)) time and Qian et al. in expected O(k2n) time for this problem.

4 A solution X is dominated by a solution Y if c(Y ) ≤ c(X) and f(Y ) ≥ f(X). The domination is strict if at least one of the inequalities is strict.

5 In addition, the EA may require that the new solution meet some requirement such as the cost being beneath a bound.

Algorithm 1 Evolutionary Algorithm for MCSC (EASC)

Input: MCSC instance parameters f : 2S → R≥0, c : 2S → R≥0, and τ, bin parameters δ ∈ [1 - cmin/c(A∗ ), 1-cmin/c(S)] and ϵ ∈ (0, 1), and number of iterations T ∈ Z≥0. t = 1, B = {∅} bin ← The bin function induced by τ, δ, ϵ ≺← The comparison operator induced by τ, bin while t ≤ T do X uniformly randomly chosen from B X′ = mutate(X) if ∃Y ∈ B such that bin(Y ) = bin(X′ ) then if Y ≺X′ then B = B \ {Y } ∪ {X′ } end if elseB = B ∪ {X′ } end if t = t +1 end while

Qian et al. (2015a) analyzed an EA for MCSC called POM (Pareto Optimization Method) [Qian et al., 2015a]. Qian et al. proved that the population of POM would contain an Hcτ 6 = O(log(cτ)) approximate solution for MCSC in O(Nn(log(n) + log(cmax) + N))) expected time, where N is the number of distinct f values in [0, τ). In order that the approximation guarantees of POM be in expected polynomial time, the number of distinct values of f in the region of [0, τ) must be bounded by a polynomial. However, this is not a realistic assumption for many applications in machine learning and data mining, where f is real-valued and easily takes on exponentially many values in the region [0, τ) [Kuhnle et al., 2017; Mirzasoleiman et al., 2015].

The N in the number of expected time comes from the population size of POM. Hence in POM, the population can get quite large, which in turn affects the expected time before the approximation ratio is reached. A similar issue arises when an EA for the dual problem of MCSC is analyzed [Qian et al., 2017]. EASC does not have this problem as its population size is always O((cmax/cmin) ln(1/ϵ)n). There exist results on approximating a set of non-dominating solutions with a set of smaller size [Laumanns et al., 2002; Horoba and Neumann, 2009]. In fact, Laumanns et al. and Horoba and Neumann both describe approaches of binning solutions that serves a similar purpose to the bins in EASC, though the bins in EASC are quite different; among other reasons, solutions that dominate others in the population of EASC are possible. However, it is not clear that the approaches described by Laumanns et al. and Horoba and Neumann could be done efficiently in this context nor could result in approximation ratios in expected polynomial time.

6 c is the minimum real number making cf(X) for all X ⊆ S and cτ integers, and the cτ harmonic number is Hcτ = ∑cτ j=1 1/j.

2 Evolutionary Algorithm for MCSC (EASC)

In this section, the algorithm EASC (Evolutionary Algorithm for Submodular Cover) is introduced. Pseudocode for EASC can be found in Algorithm 1. EASC is designed for finding good approximate solutions to instances of MCSC efficiently. As will be shown in Section 3, if the input parameter ϵ is constant and cmax/cmin is bounded by a polynomial, then EASC provides a near-feasible solution to MCSC with a constant approximation ratio in expected polynomial time.

Fundamental to EASC is a mapping from 2S to O((cmax/cmin) ln(1/ϵ)n) bins; bin j is associated with the subinterval

and a subset X ⊆ S is mapped into the bin where min{f(X), τ} falls. The population B ⊆ 2S , which is a set of subsets of S, contains at most one subset of S per bin. The bins are discussed in more detail in Section 2.1.

The input parameters ϵ ∈ (0, 1) and δ ∈ [1 - cmin/c(A∗ ), 1 - cmin/c(S)], where A∗ is an optimal solution to the instance, determine the number of bins and the intervals for each bin. Lower ϵ and δ values result in less bins, and hence a smaller population size. To find a δ in the required range, δ can be set to 1 - cmin/B where B is an upper bound on c(A∗ ) such that B ≤ c(S). In the experiments in Section 4, B is set to the cost of the greedy solution.

The number of iterations of EASC is determined by the input parameter T . At each iteration, EASC chooses a solution X ∈ B to mutate to X′ , under the mutation process described in Section 2.3. If it is not the case that X′ is mapped to a bin with a better solution according to comparison ≺, X′ is added to B, and the weaker solution is removed, if any. The comparison operator ≺ is discussed in Section 2.2.

The structure of the bins and the comparison operator ≺ are motivated by monotonicity and submodularity, as described in Sections 2.1 and 2.2.

2.1 The Bin Function

In EASC, [0, τ ] is discretized into logδ(ϵ) + 1 intervals associated with bins. Every X ⊆ S is mapped to the bin where min{f(X), τ} falls: The function bin takes X ⊆ S and returns a bin number in {0, ..., logδ(ϵ)} as follows:

The bins are depicted in Figure 1. The population B in EASC contains at most one solution for each bin, and therefore is bounded in size by logδ(ϵ) + 1. A solution X ∈ B that maps to bin logδ(ϵ) (the final bin) is near-feasible: f(X) ≥ (1-ϵ)τ. It is the solution mapped to this bin that will give the approximation ratio in expected polynomial time.

Using the fact that δ ≤ 1 - cmin/c(S), the total number of bins is bounded as follows.

Proposition 1. The number of bins is at most

Proof. It is the case that

The motivation behind the interval assignment of each bin comes from the greedy algorithm for MCSC. Suppose the sequence of elements a1, ..., ak is chosen by the greedy algorithm for the instance of MCSC. Let Ai = {a1, ..., ai}. It is the case 7 that for i < k the marginal gain at each step is lower bounded as follows:

where A∗ is an optimal solution to the instance of MCSC. If δ ≥ 1 - cmin/c(A∗ ) the region of each bin mimics this marginal gain. Intuitively, the bins can be thought of like steps in the greedy algorithm. EASC holds on to the best solution for each step.

2.2 Comparison Operator ≺

If two solutions in B map to the same bin, then the weaker solution is removed. Weaker is determined by the comparison operator ≺. ≺ uses a novel measure of cost-effectiveness, φ, in order to compare solutions. Let X ⊆ S. If bin(X) = 0 or bin(X) = logδ(ϵ), then φ(X) = c(X). Otherwise

Notice that lower φ means better cost-effectiveness. Then Y ≺ X if and only if bin(X) = bin(Y ) and φ(X) < φ(Y ).

Figure 2 illustrates the cost-effectiveness φ(X) for varying values of c(X) and f(X) for bin(X) ∈ {1, ..., logδ(ϵ) - 1}. Lower values of c(X) and higher values of f(X) result in lower φ(X) (which means more cost-effective). But as f(X) decreases, differences in c(X) are amplified in φ(X). Therefore, c matters more when comparing solutions in lower bins, and in higher bins (excluding the last) f matters more. This encourages solutions in B to rise up (via mutation) to the final bin, where a (1 - ϵ)-feasible solution is held.

7 See the Appendix in the full version of the paper.

Like the bins discussed in Section 2.1, the motivation for ≺ is the greedy algorithm for MCSC. Again, consider the sequence of elements chosen by the greedy algorithm a1, ..., ak and let Ai = {a1, ..., ai}. For i < k it is the case 8 that

Therefore at every iteration the greedy algorithm has a solution Ai where φ(Ai) ≤ c(A∗ ). In a sense, a solution X ⊆ S such that φ(X) ≤ c(A∗ ) has as good of cost-effectiveness as solutions picked by the greedy algorithm. ≺ ensures that if B contains a solution X such that φ(X) ≤ c(A∗ ), then X cannot be replaced with a solution that is less good in that sense.

2.3 Mutation of Elements in B

Random mutation of solutions in the population occur in the same fashion as existing Pareto optimization algorithms [Qian et al., 2015b]. At each iteration of EASC, an element X ∈ B is chosen uniformly randomly to be mutated. X is mutated into X′ as follows: Every x ∈ X is removed from X with independent probability 1/n. Every x /∈ X is added to X with independent probability 1/n. The number of elements expected to change fromX to X′ is 1.

X′ is added to B if there does not exist a Y ∈ B mapping to the same bin as X′ such that X′ ≺ Y . If no such Y exists, then X′ is added to B and any existing solution in the bin of X′ is removed.

3 Approximation Results

In this section, the number of iterations before EASC contains a near-feasible solution for MCSC with an approximation ratio of ln(1/ϵ)+1 is analyzed, where ϵ ∈ (0, 1) is an input parameter of EASC. Each iteration of EASC involves exactly one evaluation each of f and c. If time is measured in evaluations of f and c, as is commonly done [Badanidiyuru and Vondr´ak, 2014], then the expected time is a constant times the expected number of iterations.

The approximation guarantee in Theorem 1 is a bicriteria approximation guarantee, which means that both the feasibility constraint 9 and the minimum cost are approximated. Algorithms with bicriteria approximation guarantees have previously been considered for submodular optimization problems [Iyer and Bilmes, 2013].

If ϵ is assumed to be a constant and cmax/cmin bounded by a polynomial in n, then Theorem 1 shows that EASC finds a near-feasible solution with a constant approximation ratio in expected polynomial iterations.

8 See the Appendix in the full version of the paper.

9 The set X is feasible iff f(X) ≥ τ .

Theorem 1. Suppose that we have an instance of MCSC with optimal solution A∗ ̸= ∅, and EASC is run indefinitely with input ϵ ∈ (0, 1) and δ ∈ [1 - cmin/c(A∗ ), 1 - cmin/c(S)]. Then B contains a set A in bin logδ(ϵ) such that f(A) ≥ (1- ϵ)τ and

where A∗ is an optimum solution, in expected number of iterations at most

Once a solution that fits the criteria of Theorem 1 appears in bin logδ(ϵ), it cannot be replaced by one that does not since the comparison operator ≺ compares based on only c in the last bin. Notice that Theorem 1 does not contradict the optimality of the ln(n)-approximation ratio for the set cover problem [Feige, 1998], since the guarantee is bicriteria. The same bicriteria approximation guarantee in Theorem 1 holds for the greedy algorithm 10 .

The proof of Theorem 1 tracks cost-effective solutions in B over the duration of EASC. A set X is cost-effective if it satisfies one of the following (mutually exclusive) conditions:

Once a cost-effective set is in the final bin, a solution that meets the criteria of Theorem 1 is in the population. By design, EASC never replaces a cost-effective solution in its population with one that is not cost-effective. In addition, because of the requirement that δ ≥ 1 - cmin/c(A∗ ), the bins are structured tightly enough so that there is a significant probability that cost-effective solutions mutate into cost-effective solutions in strictly greater bins. Together, these points enable EASC to contain a cost-effective solution in its final bin in polynomial expected iterations.

The following lemmas will be used to prove Theorem 1. The lemmas are not novel to this work, but have previously been used to analyze the approximation guarantee of the greedy algorithm for MCSC [Goyal et al., 2013]. Proofs of the lemmas are included in the Appendix in the full version of the paper.

Lemma 1. Suppose that we have an instance of MCSC with optimal solution A∗ ̸= ∅. Let X ⊆ S and x∗ = argmaxx∈S ∆fτ (X, x)/c(x). Then

10 This result was originally proven for an influence application by Goyal et al. (2013) but holds for general MCSC. See the Appendix in the full version of the paper for the proof.

Lemma 2. Suppose that we have an instance of MCSC with optimal solution A∗ ̸= ∅. Let X ⊆ S such that f(X) < τ and x∗ = argmaxx∈S ∆fτ (X, x)/c(x). Then c(x∗ ) ≤ c(A∗ ).

Proof of Theorem 1. Recall that notation is defined in Section 1. For brevity, let r = logδ(ϵ) be the final bin.

There always exists at least one cost-effective solution in B: The empty set is cost-effective since φ(∅) = c(∅) = 0 < c(A∗ ), and the empty set is never removed from B because there does not exist Y ⊆ S such that c(Y ) < 0 = c(∅). Note that this means if a solution is removed from B, it can be assumed that it did not correspond to bin 0.

Define an infinite sequence ℓt, t ∈ {1, 2, ...}, where ℓt is the max value in {0, ..., r} such that there exists a cost-effective solution X ∈ B where bin(X) = ℓt at the beginning of iteration t of EASC.

Part One. First, it is shown that the sequence ℓt is nondecreasing. Let X be the cost-effective set corresponding to ℓt at the beginning of iteration t. If X is not removed from B during the tth iteration, then clearly ℓt ≤ ℓt+1.

Suppose X is removed from B during the tth iteration. Then X was replaced with X′ such that X ≺ X′ and bin(X) = bin(X′ ). Let b = bin(X) = bin(X′ ). As explained above, b ̸= 0. Suppose b = r. Then X ≺ X′ implies that c(X′ ) < c(X) ≤ (ln(1/ϵ) + 1) c(A∗ ). Therefore X′ is costeffective. If b ∈ {1, ..., r - 1}. Then X ≺ X′ implies that φ(X′ ) < φ(X) ≤ c(A∗ ) and hence X′ is also cost-effective. In both of these cases, ℓt = ℓt+1.

Part Two. Second, it is shown that if bin(X) < r and

then bin(X ∪ {x∗ }) > bin(X).

Let a = bin(X). Lemma 1 and that δ ≥ 1 - cmin/c(A∗ ) implies

By definition of the bins fτ (X) ≥ (1 - δa )τ , and therefore

Since a < r, it is the case that bin(X ∪ {x∗ }) ≥ a + 1.

Part Three. Third, it is shown that if X is cost-effective, bin(X) < r, and x∗ defined as in Part Two, then X ∪ {x∗ } is cost-effective. Let a = bin(X) and b = bin(X ∪ {x∗ }). To show the cost-effectiveness of X ∪ {x∗ }, four cases are analyzed based on the values of a and b.

Case (i): b < r and a = 0. In this case, X = ∅ as explained at the beginning of the proof, and X ∪ {x∗ } = {x∗ }. Lemma 1 states that

which can be re-arranged to see that φ(x∗ ) ≤ c(A∗ ) and hence X ∪ {x∗ } is cost-effective.

Case (ii): b < r and a > 0. Since b, a < r it is the case that fτ (X ∪ {x∗ }) = f(X ∪ {x∗ }) and fτ (X) = f(X). Lemma 1 gives that

Using the upper bound on τ - f(X) given by re-arranging φ(X) ≤ c(A∗ ) implies that

which may be re-arranged to see that X ∪ {x∗ } is costeffective.

Case (iii): b = r and a > 0. X being cost-effective and a < r imply that c(X ∪ {x∗ }) =

By Lemma 2, c(x∗ ) ≤ c(A∗ ). Therefore X ∪ {x∗ } is costeffective.

Case (iv): b = r and a = 0. Then X = ∅ as explained at the beginning of the proof. Then c(X ∪ {x∗ }) = c(x∗ ) ≤ c(A∗ ) by Lemma 2, and therefore X ∪ {x∗ } is cost-effective.

Part Four. It is now shown that if at iteration t, the costeffective set X associated with ℓt < r is mutated into X ∪ {x∗ }, then ℓt < ℓt+1.

Suppose X is mutated into X ∪ {x∗ } on iteration t. X ∪ {x∗ } is cost-effective by Part Three. Let b = bin(X ∪ {x∗ }). By Part Two, b > ℓt. If there does not exist Y ∈ B at the beginning of iteration t such that bin(Y ) = b, then X ∪{x∗ } is added to B. Then ℓt+1 = b.

Suppose there does exist a Y ∈ B at the beginning of iteration t such that bin(Y ) = b. Y is not cost-effective by definition of ℓt. Then if b = r,

and so Y ≺ X ∪ {x∗ }. Then Y is replaced with X ∪ {x∗ } in B. If b < r, and recalling that b ̸= 0 as explained at the beginning of the proof, then

Therefore again Y ≺ X ∪ {x∗ }, so Y is replaced with X ∪ {x∗ } in B. In both cases, ℓt+1 = b.

Part Five. Finally, the expected number of iterations until ℓt = r is analyzed. Once ℓt = r, the solution in B mapping to bin r satisfies the conditions of the theorem statement.

Suppose it is the beginning of iteration t of EASC such that ℓt < r. Then with probability at least

the set X corresponding to ℓt will be chosen and mutated into X∪{x∗ }. By Part Four, if this occurs ℓt < ℓt+1. By Part One, the sequence is non-decreasing. This means that the expected number of steps for ℓt to reach r is at most enr(r + 1). The bound on r given by Proposition 1 of Section 2.1 gives the theorem statement.

4 Experimental Analysis

In this section, EASC is experimentally evaluated on instances of the Influence Threshold Problem (IT) [Goyal et al., 2013], a special case of MCSC. EASC is compared to the greedy algorithm and POM [Qian et al., 2015a]. In all experiments, EASC and POM find solutions of lower cost than the greedy algorithm, and in most cases EASC converges faster than POM to a low cost. Code to run the experiments is publicly available at https://gitlab.com/vcrawford/easc.git.

4.1 Application and Setup

The experiments are run on instances of the Influence Threshold Problem, defined as follows. Let G = (V, E) be a social network where vertices V represents users, and directed edges E represent social connections. Activation of users in the social network starts from an initial seed set and then propagates across "live edges" according to the independent cascade model [Kempe et al., 2003], in which every edge (u, v) ∈ E has an independent probability puv of being live.

For every user v ∈ V , there is a cost cv of seeding that user. The cost of seeding a set X is c(X) = ∑x∈X cx. The function f(X) is the expected number of users that will become active if X is seeded; f is monotone submodular [Kempe et al., 2003]. Then the IT problem is defined as follows: given an activation threshold τ , find argmin{c(X) : X ⊆ S, f(X) ≥ τ }.

The experiments are run on four real social networks from SNAP [Leskovec and Krevl, 2015]: ca-GrQc (n = 5242), ca-HepPh (n = 12008), wiki-Vote (n = 7115), and egoFacebook (n = 4039). The independent cascade model is used to model activation from a seed set for the above four social networks with constant edge probabilities p = 0.07, p = 0.02, p = 0.04, and p = 0.013, respectively.

Computing the expected activation f(X) under the independent cascade model is #P-hard [Chen et al., 2010]. Instead of evaluating f directly, the reverse influence sampling approach [Borgs et al., 2014] with 100,000 samples is used in order to approximate f. The same set of samples is used for all algorithms on a data set.

The cost function c(X) = ∑x∈X cx, where every node v in the social network is assigned a cost cv that is its outgoing degree perturbed by random multiplicative noise 11 In particular, node v with outdoing degree d has cost 1 + (1 + |ξ|)d where ξ ∼ N (µ = 0, σ = 0.5)12 .

11 Under this model of cost, social network users with more outgoing edges are generally more expensive to seed, but individual preferences factor into the price of seeding via random noise.

12 A normal distribution with mean 0 and standard deviation 0.5.

The instance of MCSC for each social network is run with a different threshold τ. The greedy algorithm is run with input τ and ϵ = 0.05. EASC is run with τ, ϵ = 0.05, and δ = 1 - cmin/B where B is the cost of the output of the greedy algorithm when run with τ and ϵ = 0. POM is run with threshold (1 - ϵ)τ for fair comparison with EASC, although POM is not a bicriteria algorithm. EASC and POM are run 3 times on each instance, and the results are averaged.

4.2 Results

The experimental results are plotted in Figure 3. At small intervals over the duration of EASC and POM, the minimum cost of any solution in the population with f value above (1 - ϵ)τ is plotted. The cost and the number of f evaluations are normalized by that of the greedy algorithm. That is, if the greedy algorithm returned a set G, then the costs plotted are normalized by c(G) and the number of function evaluations are normalized by n|G|.

In all experiments, EASC and POM were able to find a better solution than the greedy algorithm. In ca-HepPh (Figure 3(b)), both EASC and POM find a better solution than the greedy algorithm in less f evaluations. These results demonstrate an ability to improve on the solution quality of the greedy algorithm.

In ca-GrQc (Figure 3(a)) and wiki-Vote (Figure 3(c)), EASC finds a better solution more quickly than POM throughout the entire experiment. In contrast, in ca-HepPh (Figure 3(b)) and ego-Facebook (Figure 3(d)) POM finds a better solution more quickly in the earlier stages of the experiment, but EASC catches up and either outperforms POM for the remainder of the iterations (caHepPh) or converges to about the same performance. This behavior may be explained by the fact that at first POM has a smaller population since every solution competes with every other solution, unlike EASC where competition is restricted to within bins. But as the population of POM gets larger (at least 3 times larger than EASC at the end of these experiments), the improvement of POM is slowed.

Acknowledgements

Victoria G. Crawford was supported by a Harris Corporation Fellowship. Alan Kuhnle provided helpful feedback in preparation of the manuscript.