## An Efficient Evolutionary Algorithm for Minimum Cost Submodular Cover

Victoria G. Crawford 1,*

1 University of Florida *

vcrawford01@ufl.edu

## Abstract

In this paper, the Minimum Cost Submodular Cover problem is studied, which is to minimize a modular cost function such that the monotone submodular benefit function is above a threshold. For this problem, an evolutionary algorithm EASC is introduced that achieves a constant, bicriteria approximation in expected polynomial time; this is the first polynomial-time evolutionary approximation algorithm for Minimum Cost Submodular Cover. To achieve this running time, ideas motivated by submodularity and monotonicity are incorporated into the evolutionary process, which likely will extend to other submodular optimization problems. In a practical application, EASC is demonstrated to outperform the greedy algorithm and converge faster than competing evolutionary algorithms for this problem.

## 1 Introduction

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

- i. For all A ⊆ B ⊆ S f A , ( ) ≤ f ( B ) (monotonicity).
- ii. For all A ⊆ B ⊆ S and x / B ∈ , f ( A ∪ { x } ) -f ( A ) ≥ f ( B ∪ { x } ) -f ( B ) (submodularity).

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.

Problem 1 (Minimum Cost Submodular Cover (MCSC)) . Let S be a ground set of size n . Let c : 2 S → R ≥ 0 be a modular 1 function such that c X ( ) = 0 if and only if X = ∅ , and f : 2 S → 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.

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].

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

2 The greedy algorithm is discussed in Section 5.1 of the Appendix.

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 -glyph[epsilon1] ) τ and c A ( ) ≤ (ln(1 /glyph[epsilon1] ) +1) ( c A ∗ ) , where A ∗ is an optimum solution and glyph[epsilon1] ∈ (0 1) , is an input parameter. The expected time is O ( n 3 (( c max /c min ) ln(1 /glyph[epsilon1] )) 2 ) , where c max and c min are the maximum and minimum cost of a single element s ∈ S , respectively. If c max /c min is bounded by a polynomial in n and glyph[epsilon1] 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,a, 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 c min = min x ∈ S c x ( ) , and c max = max x ∈ 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 → e a .

## 1.2 Related Work

Evolutionary algorithms (EAs) have previously been analyzed for submodular optimization problems [Friedrich and Neumann, 2015, Qian et al., 2015a,b, 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.

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

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)

```
Algorithm 1 Evolutionary Algorithm for MCSC (EASC)
    Input : MCSC instance parameters f : 2^s
```

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 ( n 2 (log( n ) + k )) time and Qian et al. in expected O ( k n 2 ) time for this problem.

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 H cτ 6 = O (log( cτ )) approximate solution for MCSC in O ( Nn (log( n ) + log( c max ) + 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 (( c max /c min ) ln(1 /glyph[epsilon1] ) 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 H cτ = ∑ cτ j =1 1 /j .

Figure 1: The region [0 , τ ] is discretized into log δ ( glyph[epsilon1] ) + 1 bins in EASC. Solutions X ⊆ S are mapped into the bin corresponding to the region where min { f ( X ,τ ) } falls. B contains at most 1 subset of S for each bin.

|   bin 0 | bin 1    | bin 2            | bin log δ ( glyph[epsilon1] )   |
|---------|----------|------------------|---------------------------------|
|       0 | (1 - δ 2 | ) τ (1 - δ 3 ) τ | (1 - glyph[epsilon1] ) τ τ      |

## 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 glyph[epsilon1] is constant and c max /c min 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 2 S to O (( c max /c min ) ln(1 /glyph[epsilon1] ) n ) bins; bin j is associated with the subinterval

$$\left [ \left ( 1 - \delta ^ { j } \right ) \tau, \left ( 1 - \delta ^ { j + 1 } \right ) \tau \right ) \subseteq \left [ 0, \tau \right ],$$

and a subset X ⊆ S is mapped into the bin where min { f ( X ,τ ) } falls. The population B ⊆ 2 S , 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 glyph[epsilon1] ∈ (0 1) , and δ ∈ [1 -c min /c A ( ∗ ) , 1 -c min /c S ( )] , where A ∗ is an optimal solution to the instance, determine the number of bins and the intervals for each bin. Lower glyph[epsilon1] and δ values result in less bins, and hence a smaller population size. To find a δ in the required range, δ can be set to 1 -c min /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 δ ( glyph[epsilon1] ) + 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 δ ( glyph[epsilon1] ) } as follows:

$$\text{bin} ( X ) = \begin{cases} i & \text{if $(1-\delta^{i})\tau\leq f(X)<(1-\delta^{i+1})\tau$} \\ & \text{for an $i\in\{0,\dots,\log_{\delta}(\epsilon)-1\}$} \\ \log _ { \delta } ( \epsilon ) & \text{if $f(X)\geq (1-\epsilon)\tau$}. \end{cases}$$

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 δ ( glyph[epsilon1] ) + 1 . A solution X ∈ B that maps to bin log δ ( glyph[epsilon1] ) (the final bin) is near-feasible: f ( X ) ≥ (1 -glyph[epsilon1] ) τ . It is the solution mapped to this bin that will give the approximation ratio in expected polynomial time.

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

## Proposition 1. The number of bins is at most

$$\frac { c _ { m a x } } { c _ { m i n } } \ln \left ( \frac { 1 } { \epsilon } \right ) n + 1.$$

Figure 2: An illustration of the cost-effectiveness φ for X where bin ( X ) ∈ { 1 , ..., log δ ( glyph[epsilon1] ) - } 1 . On both the c X ( ) and f ( X ) axis, left is greater. Lower values of φ X ( ) means more cost-effective.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01029v1-figure-48070c82-ee8c-42ee-bd90-b716ff0a7993.jpg)

## Proof. It is the case that

$$\log _ { \delta } ( \epsilon ) = \frac { \ln ( \epsilon ) } { \ln \delta } = \frac { \ln ( 1 / \epsilon ) } { - \ln \delta } \leq \frac { \ln ( 1 / \epsilon ) } { 1 - \delta } \leq \frac { c ( S ) } { c _ { m i n } } \ln \left ( \frac { 1 } { \epsilon } \right ).$$

Since c S ( ) ≤ c max n , the result follows.

The motivation behind the interval assignment of each bin comes from the greedy algorithm for MCSC. Suppose the sequence of elements a , ..., a 1 k is chosen by the greedy algorithm for the instance of MCSC. Let A i = { a , ..., a 1 i } . It is the case 7 that for i &lt; k the marginal gain at each step is lower bounded as follows:

$$f ( A _ { i + 1 } ) - f ( A _ { i } ) \geq \frac { c ( a _ { i } ) } { c ( A ^ { * } ) } \left ( \tau - f ( A _ { i } ) \right )$$

where A ∗ is an optimal solution to the instance of MCSC. If δ ≥ 1 -c min /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 δ ( glyph[epsilon1] ) , then φ X ( ) = c X ( ) . Otherwise

$$\phi ( X ) = c ( X ) / \ln \left ( \frac { \tau } { \tau - f ( X ) } \right ).$$

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

Figure 2 illustrates the cost-effectiveness φ X ( ) for varying values of c X ( ) and f ( X ) for bin ( X ) ∈ { 1 , ..., log δ ( glyph[epsilon1] ) - } 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 -glyph[epsilon1] ) -feasible solution is held.

7 See Proposition 2 of Section 5.1 in the Appendix.

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 a , ..., a 1 k and let A i = { a , ..., a 1 i } . For i &lt; k it is the case 8 that

$$c ( A _ { i } ) / \ln \left ( \frac { \tau } { \tau - f ( A _ { i } ) } \right ) \leq c ( A ^ { * } ).$$

Therefore at every iteration the greedy algorithm has a solution A i where φ A ( i ) ≤ 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 from X 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 /glyph[epsilon1] ) + 1 is analyzed, where glyph[epsilon1] ∈ (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 glyph[epsilon1] is assumed to be a constant and c max /c min 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.

glyph[negationslash]

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

$$c ( A ) \leq \left ( \ln \left ( \frac { 1 } { \epsilon } \right ) + 1 \right ) c ( A ^ { * } ),$$

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

$$\ e n \left ( \left ( \frac { c _ { m a x } } { c _ { m i n } } \right ) \ln \left ( \frac { 1 } { \epsilon } \right ) n + 1 \right ) ^ { 2 }.$$

Once a solution that fits the criteria of Theorem 1 appears in bin log δ ( glyph[epsilon1] ) , 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],

8 See Proposition 2 of Section 5.1 in the Appendix.

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

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:

$$i. \, \text{bin} ( X ) < \log _ { \delta } ( \epsilon ) \, \text{and} \, \phi ( X ) \leq c ( A ^ { * } ).$$

$$\text{ii. bin} ( X ) = \log _ { \delta } ( \epsilon ) \, \text{and} \, c ( X ) \leq ( \ln ( 1 / \epsilon ) + 1 ) \, c ( A ^ { * } ).$$

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 -c min /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 Section 5.2 of the Appendix.

glyph[negationslash]

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

$$\tau - f _ { \tau } ( X \cup \{ x ^ { * } \} ) \leq \left ( 1 - \frac { c ( x ^ { * } ) } { c ( A ^ { * } ) } \right ) ( \tau - f _ { \tau } ( X ) ).$$

glyph[negationslash]

Lemma 2. Suppose that we have an instance of MCSC with optimal solution A ∗ = ∅ . Let X ⊆ S such that f ( X &lt; τ ) and x ∗ = argmax x ∈ 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 ( ) δ glyph[epsilon1] be the final bin. There always exists at least one cost-effective solution in B : The empty set is cost-effective since φ ( ∅ ) = c ( ∅ ) = 0 &lt; c A ( ∗ ) , and the empty set is never removed from B because there does not exist Y ⊆ S such that c Y ( ) &lt; 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 glyph[lscript] t , t ∈ { 1 2 , , ... } , where glyph[lscript] t is the max value in { 0 , ..., r } such that there exists a cost-effective solution X ∈ B where bin ( X ) = glyph[lscript] t at the beginning of iteration t of EASC.

Part One. First, it is shown that the sequence glyph[lscript] t is non-decreasing. Let X be the cost-effective set corresponding to glyph[lscript] t at the beginning of iteration t . If X is not removed from B during the t th iteration, then clearly glyph[lscript] t ≤ glyph[lscript] t +1 .

glyph[negationslash]

Suppose X is removed from B during the t th 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 ( ′ ) &lt; c X ( ) ≤ (ln(1 /glyph[epsilon1] ) + 1) c A ( ∗ ) . Therefore X ′ is cost-effective. If b ∈ { 1 , ..., r - } 1 . Then X ≺ X ′ implies that φ X ( ′ ) &lt; φ X ( ) ≤ c A ( ∗ ) and hence X ′ is also cost-effective. In both of these cases, glyph[lscript] t = glyph[lscript] t +1 .

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

$$x ^ { * } = \arg \max _ { x \in S } \frac { \Delta f _ { \tau } ( X, x ) } { c ( x ) },$$

then bin ( X ∪ { x ∗ } ) &gt; bin ( X ) .

10 This result was originally proven for an influence application by Goyal et al. (2013) but holds for general MCSC. See Proposition 2 of Section 5.1 in the Appendix.

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

$$f _ { \tau } ( X \cup \{ x ^ { * } \} ) \geq ( 1 - \delta ) \tau + \delta f _ { \tau } ( X ).$$

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

$$f _ { \tau } ( X \cup \{ x ^ { * } \} ) \geq ( 1 - \delta ^ { a + 1 } ) \tau.$$

Since a &lt; 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 &lt; 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 &lt; r and a = 0 . In this case, X = ∅ as explained at the beginning of the proof, and X ∪ { x ∗ } = { x ∗ } . Lemma 1 states that

$$\tau - f _ { \tau } ( x ^ { * } ) \leq \left ( 1 - \frac { c ( x ^ { * } ) } { c ( A ^ { * } ) } \right ) \tau \leq \exp \left ( - \frac { c ( x ^ { * } ) } { c ( A ^ { * } ) } \right ) \tau$$

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

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

$$\tau - f ( X \cup \{ x ^ { * } \} ) \leq \exp \left ( - \frac { c ( x ^ { * } ) } { c ( A ^ { * } ) } \right ) ( \tau - f ( X ) ).$$

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

$$\tau - f ( X \cup \{ x ^ { * } \} ) \leq \exp \left ( - \frac { c ( X \cup \{ x ^ { * } \} ) } { c ( A ^ { * } ) } \right ) \tau$$

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

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

$$c ( X ) + c ( x ^ { * } ) \leq \ln \left ( \frac { \tau } { \tau - f ( X ) } \right ) c ( A ^ { * } ) + c ( x ^ { * } ).$$

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

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 cost-effective set X associated with glyph[lscript] t &lt; r is mutated into X ∪ { x ∗ } , then glyph[lscript] t &lt; glyph[lscript] 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 &gt; glyph[lscript] 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 glyph[lscript] 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 glyph[lscript] t . Then if b = r ,

$$c ( X \cup \{ x ^ { * } \} ) \leq ( \ln ( 1 / \epsilon ) + 1 ) c ( A ^ { * } ) < c ( Y )$$

glyph[negationslash]

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

$$\phi ( X \cup \{ x ^ { * } \} ) \leq c ( A ^ { * } ) < \phi ( Y ).$$

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

({(}(√(⌉(∐(⌈(](︷(˜(̂(((̂

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01029v1-figure-14f468af-7ccb-418e-a331-89354f033e9f.jpg)

({(}(√(⌉(∐(⌈(](︷(˜(̂(((̂

({(}(√(⌉(∐(⌈(](︷(˜(̂(((̂

({(}(√(⌉(∐(⌈(](︷(˜(̂(((̂

(˜(√(˜(˜(̂(glyph[arrowbt]

Figure 3: Over the duration of EASC and POM, the minimum cost of any solution in the population with f value above (1 -glyph[epsilon1] ) τ is plotted. Both cost and number of f evaluations are normalized by that of the greedy algorithm.

Part Five. Finally, the expected number of iterations until glyph[lscript] t = r is analyzed. Once glyph[lscript] 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 glyph[lscript] t &lt; r . Then with probability at least

$$\frac { 1 } { | \mathcal { B } | } \frac { 1 } { n } \left ( 1 - \frac { 1 } { n } \right ) ^ { n - 1 } \geq \frac { 1 } { e n ( r + 1 ) }$$

the set X corresponding to glyph[lscript] t will be chosen and mutated into X ∪{ x ∗ } . By Part Four, if this occurs glyph[lscript] t &lt; glyph[lscript] t +1 . By Part One, the sequence is non-decreasing. This means that the expected number of steps for glyph[lscript] 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 p uv of being live.

For every user v ∈ V , there is a cost c v of seeding that user. The cost of seeding a set X is c X ( ) = ∑ x ∈ X c x . 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 ego-Facebook ( 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 c x , where every node v in the social network is assigned a cost c v 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 .

The instance of MCSC for each social network is run with a different threshold τ . The greedy algorithm is run with input τ and glyph[epsilon1] = 0 05 . . EASC is run with τ , glyph[epsilon1] = 0 05 . , and δ = 1 -c min /B where B is the cost of the output of the greedy algorithm when run with τ and glyph[epsilon1] = 0 . POM is run with threshold (1 -glyph[epsilon1] ) τ 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 -glyph[epsilon1] ) τ 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.

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 . .

## References

- A. Badanidiyuru and J. Vondr´ ak. Fast algorithms for maximizing submodular functions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 1497-1514. SIAM, 2014.
- C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 946-957. SIAM, 2014.
- W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining , pages 1029-1038. ACM, 2010.
- U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM) , 45(4):634-652, 1998.
- T. Friedrich and F. Neumann. Maximizing submodular functions under matroid constraints by multi-objective evolutionary algorithms. In International Conference on Parallel Problem Solving from Nature , pages 922-931. Springer, 2014.
- T. Friedrich and F. Neumann. Maximizing submodular functions under matroid constraints by evolutionary algorithms. Evolutionary computation , 23(4):543-558, 2015.
- T. Friedrich, A. G¨bel, F. Quinzan, and M. Wagner. o Heavy-tailed mutation operators in single-objective combinatorial optimization. In International Conference on Parallel Problem Solving from Nature , pages 134-145. Springer, 2018.
- A. Goyal, F. Bonchi, L. V. Lakshmanan, and S. Venkatasubramanian. On minimizing budget and time in influence propagation over social networks. Social network analysis and mining , 3(2):179-192, 2013.
- A. Guillory and J. A. Bilmes. Simultaneous learning and covering with adversarial noise. In ICML , volume 11, pages 369-376, 2011.
- C. Horoba and F. Neumann. Additive approximations of pareto-optimal sets by evolutionary multi-objective algorithms. In Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms , pages 79-86. ACM, 2009.
- R. K. Iyer and J. A. Bilmes. Submodular optimization with submodular cover and submodular knapsack constraints. In Advances in Neural Information Processing Systems , pages 2436-2444, 2013.
- D. Kempe, J. Kleinberg, and E. Tardos. ´ Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining , pages 137-146. ACM, 2003.
- A. Kuhnle, T. Pan, M. A. Alim, and M. T. Thai. Scalable bicriteria algorithms for the threshold activation problem in online social networks. In INFOCOM 2017-IEEE Conference on Computer Communications, IEEE , pages 1-9. IEEE, 2017.
- M. Laumanns, L. Thiele, K. Deb, and E. Zitzler. Combining convergence and diversity in evolutionary multiobjective optimization. Evolutionary computation , 10(3):263-282, 2002.
- J. Leskovec and A. Krevl. { SNAP Datasets } { : Stanford } large network dataset collection. 2015.
- B. Mirzasoleiman, A. Karbasi, A. Badanidiyuru, and A. Krause. Distributed submodular cover: Succinctly summarizing massive data. In Advances in Neural Information Processing Systems , pages 2881-2889, 2015.

- B. Mirzasoleiman, M. Zadimoghaddam, and A. Karbasi. Fast distributed submodular cover: Public-private data summarization. In Advances in Neural Information Processing Systems , pages 3594-3602, 2016.
- G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming , 14(1):265-294, 1978.
- A. Norouzi-Fard, A. Bazzi, I. Bogunovic, M. El Halabi, Y.-P. Hsieh, and V. Cevher. An efficient streaming algorithm for the submodular cover problem. In Advances in Neural Information Processing Systems , pages 4493-4501, 2016.
- C. Qian, Y. Yu, and Z.-H. Zhou. On constrained boolean pareto optimization. In IJCAI , pages 389-395, 2015a.
- C. Qian, Y. Yu, and Z.-H. Zhou. Subset selection by pareto optimization. In Advances in Neural Information Processing Systems , pages 1774-1782, 2015b.
- C. Qian, J.-C. Shi, Y. Yu, and K. Tang. On subset selection with general cost constraints. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-2017) , pages 2613-2619, 2017.
- L. A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica , 2(4):385-393, 1982.

## Algorithm 2 Greedy Algorithm

Input: MCSC instance parameters f : 2 S → R ≥ 0 , c : 2 S → R ≥ 0 , and τ , and glyph[epsilon1] ∈ (0 , 1) .

$$\begin{array} { l l } \text{Input: MCSC instance parameters $f\colon 2^{\geq}$} \\ A = \emptyset \\ \text{while $f(A) < (1-\epsilon)\tau$ do} \\ u = \argmax_{x\in S} \Delta f _ { \tau } ( A, x ) / c ( x ) \\ A = A \cup \{ u \} \\ \text{end while} \\ \text{return: $A$} \end{array}$$

## 5 Appendix

Background and results that are not included in the paper due to space constraints are provided here. In particular, the greedy algorithm and its approximation guarantee for MCSC is discussed in Section 5.1. Lemmas needed for the proof of Theorem 1 are proven in Section 5.2.

## 5.1 The Greedy Algorithm

Pseudocode for the greedy algorithm is provided in Algorithm 2. It should be noted that the classic greedy algorithm is Algorithm 2 with glyph[epsilon1] = 0 , but this alternate version is considered since it is more comparable to EASC.

As Proposition 2 states, the bicriteria approximation ratio proven for EASC in Section 3 also holds for the greedy algorithm. This result is not novel to this paper, but was proven in the context of influence by Goyal et al. (2013). The proof is easily adjusted to hold for general MCSC, and the proof is included here.

glyph[negationslash]

Proposition 2. Suppose that we have an instance of MCSC with optimal solution A ∗ = ∅ , and run Algorithm 2 with input glyph[epsilon1] &gt; 0 . Then the set A returned satisfies f ( A ) ≥ (1 -glyph[epsilon1] ) τ and

$$c ( A ) \leq \left ( \ln \left ( \frac { 1 } { \epsilon } \right ) + 1 \right ) c ( A ^ { * } ).$$

Proof. The feasibility guarantee is clear from the stopping condition on Algorithm 2. Let A = { a , ..., a 1 k } in the order of being chosen. Denote by A i = { a , ..., a 1 i } . By Lemma 1, for any i ∈ { 1 , ..., k }

$$\begin{array} { c c c c c c } \cdot & \cdot & \cdot \cdot \cdot & \cdot \cdot \\ \tau - f _ { \tau } ( A _ { i } ) & \leq \left ( 1 - \frac { c ( a _ { i } ) } { c ( A ^ { * } ) } \right ) ( \tau - f _ { \tau } ( A _ { i - 1 } ) ) \\ & \leq \exp \left ( \frac { c ( a _ { i } ) } { c ( A ^ { * } ) } \right ) ( \tau - f _ { \tau } ( A _ { i - 1 } ) ). \end{array}$$

By induction it is then the case that

$$\tau - f _ { \tau } ( A _ { k - 1 } ) \leq \exp \left ( \frac { c ( A _ { k - 1 } ) } { c ( A ^ { * } ) } \right ) \tau.$$

Algorithm 2 did not return A k -1 , and so τ -f τ ( A k -1 ) &gt; glyph[epsilon1]τ . Applying this to Equation 1 and then re-arranging gives

$$c ( A _ { k - 1 } ) \leq \ln \left ( \frac { 1 } { \epsilon } \right ) c ( A ^ { * } ).$$

By applying Lemma 2, it is the case that

$$c ( A ) = c ( A _ { k - 1 } ) + c ( a _ { k } ) \leq \left ( \ln \left ( \frac { 1 } { \epsilon } \right ) + 1 \right ) c ( A ^ { * } ).$$

## 5.2 Lemmas

Lemmas needed for the proof of Theorem 1 of Section 3 are proven in this section. Lemma 1 is a slight variation of a commonly used result and is not novel to this paper [Nemhauser et al., 1978]. Lemma 2 is assumed without proof in the proof of Proposition 2 by Goyal et al., but is proven here for clarity.

glyph[negationslash]

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

$$\tau - f _ { \tau } ( X \cup \{ x ^ { * } \} ) \leq \left ( 1 - \frac { c ( x ^ { * } ) } { c ( A ^ { * } ) } \right ) ( \tau - f _ { \tau } ( X ) ).$$

Proof. Define an arbitrary order on the elements of A ∗ , y , ..., y 1 m . It is the case that

$$c ( A ^ { * } ) \frac { \Delta f _ { \tau } ( X, x ^ { * } ) } { c ( x ^ { * } ) } = \sum _ { i = 1 } ^ { m } c ( y _ { i } ) \frac { \Delta f _ { \tau } ( X, x ^ { * } ) } { c ( x ^ { * } ) } \geq \sum _ { i = 1 } ^ { m } \Delta f _ { \tau } ( X, y _ { i } )$$

by definition of x ∗ . Now, if f is monotone submodular, then f τ is as well, which implies

$$\sum _ { i = 1 } ^ { m } \Delta f _ { \tau } ( X, y _ { i } ) & \geq \sum _ { i = 1 } ^ { m } \Delta f _ { \tau } ( X \cup \{ y _ { 1 }, \dots, y _ { i - 1 } \}, y _ { i } ) \\ & = \tau - f _ { \tau } ( X ).$$

Therefore,

$$c ( A ^ { * } ) \frac { \Delta f _ { \tau } ( X, x ^ { * } ) } { c ( x ^ { * } ) } \geq \tau - f _ { \tau } ( X ),$$

which can be re-arranged to get the statement of the lemma.

glyph[negationslash]

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

Proof. First, it will be shown that there exists an a ∗ ∈ A ∗ such that

$$\frac { \Delta f _ { \tau } ( X, a ^ { * } ) } { c ( a ^ { * } ) } \geq \frac { \Delta f _ { \tau } ( X, A ^ { * } ) } { c ( A ^ { * } ) }.$$

Suppose no such a ∗ ∈ A ∗ existed. Then

$$\sum _ { a \in A ^ { * } } \Delta f _ { \tau } ( X, a ) < \sum _ { a \in A ^ { * } } \frac { c ( a ) } { c ( A ^ { * } ) } \Delta f _ { \tau } ( X, A ^ { * } ) = \Delta f _ { \tau } ( X, A ^ { * } )$$

which implies that f τ is not monotone submodular. However, this is a contradiction because f being monotone submodular implies that f τ is monotone submodular. Therefore such an a ∗ must exist.

f ( X ) &lt; τ implies that ∆ f τ ( X,A ∗ ) &gt; 0 , which in turn implies that ∆ f τ ( X,a ∗ ) &gt; 0 . In addition, f ( X &lt; τ ) and the submodularity of f implies that ∆ f τ ( X,x ∗ ) &gt; 0 . Then

$$c ( x ^ { * } ) \leq \frac { \Delta f _ { \tau } ( X, x ^ { * } ) } { \Delta f _ { \tau } ( X, a ^ { * } ) } c ( a ^ { * } ) \leq \frac { \Delta f _ { \tau } ( X, x ^ { * } ) } { \Delta f _ { \tau } ( X, A ^ { * } ) } c ( A ^ { * } ) \leq c ( A ^ { * } )$$

since ∆ f τ ( X,x ∗ ) ≤ ∆ f τ ( X,A ∗ ) .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01029v1-figure-0afc8e8f-27a5-42d4-9932-dcb465ec5e66.jpg)
Victoria G. Crawford
An Efficient Evolutionary Algorithm for Minimum Cost Submodular Cover
In this paper, the Minimum Cost Submodular Cover problem is studied, which is
to minimize a modular cost function such that the monotone submodular benefit
function is above a threshold. For this problem, an evolutionary algorithm EASC
is introduced that achieves a constant, bicriteria approximation in expected
polynomial time; this is the first polynomial-time evolutionary approximation
algorithm for Minimum Cost Submodular Cover. To achieve this running time,
ideas motivated by submodularity and monotonicity are incorporated into the
evolutionary process, which likely will extend to other submodular optimization
problems. In a practical application, EASC is demonstrated to outperform the
greedy algorithm and converge faster than competing evolutionary algorithms for
this problem.