Maximizing Non-monotone/Non-submodular Functions by
Multi-objective Evolutionary Algorithms
Chao Qian1 , Yang Yu2 , Ke Tang3 , Xin Yao3 , Zhi-Hua Zhou2∗

arXiv:1711.07214v1 [] 20 Nov 2017

1 Anhui

Province Key Lab of Big Data Analysis and Application, University of Science and Technology of China, Hefei, China
2 National Key Lab for Novel Software Technology,

3 Shenzhen

Nanjing University, Nanjing, China

Key Lab of Computational Intelligence, Southern University of Science and Technology, Shenzhen, China

Abstract

Evolutionary algorithms (EAs) are a kind of nature-inspired general-purpose optimization algorithm, and have shown empirically good performance in solving various real-word optimization
problems. However, due to the highly randomized and complex behavior, the theoretical analysis of EAs is difficult and is an ongoing challenge, which has attracted a lot of research attentions.
During the last two decades, promising results on the running time analysis (one essential theoretical aspect) of EAs have been obtained, while most of them focused on isolated combinatorial
optimization problems, which do not reflect the general-purpose nature of EAs. To provide a general theoretical explanation of the behavior of EAs, it is desirable to study the performance of EAs
on a general class of combinatorial optimization problems. To the best of our knowledge, this direction has been rarely touched and the only known result is the provably good approximation guarantees of EAs for the problem class of maximizing monotone submodular set functions with matroid constraints, which includes many NP-hard combinatorial optimization problems. The aim of
this work is to contribute to this line of research. As many combinatorial optimization problems
also involve non-monotone or non-submodular objective functions, we consider these two general
problem classes, maximizing non-monotone submodular functions without constraints and maximizing monotone non-submodular functions with a size constraint. We prove that a simple multiobjective EA called GSEMO can generally achieve good approximation guarantees in polynomial
expected running time.
Key words: Evolutionary algorithms, submodular optimization, multi-objective evolutionary
algorithms, running time analysis, computational complexity

∗ Corresponding

author
Email addresses: chaoqian@ustc.edu.cn (Chao Qian1 ), yuy@nju.edu.cn (Yang Yu2 ), tangk3@sustc.edu.cn (Ke Tang3 ),
xiny@sustc.edu.cn (Xin Yao3 ), zhouzh@nju.edu.cn (Zhi-Hua Zhou2 )

Preprint submitted for review

November 21, 2017

1. Introduction

Evolutionary algorithms (EAs) [3] are a kind of randomized metaheuristic optimization algorithm,
inspired by the evolution process of natural species, i.e., natural selection and survival of the fittest.
Starting from a random population of solutions, EAs iteratively apply reproduction operators to generate a set of offspring solutions from the current population, and then apply a selection operator
to weed out bad solutions. EAs have been applied to diverse areas (e.g., antenna design [18], bioinformatics [23] and data mining [24]) and can produce human-competitive results [20]. Compared
with the application, the theoretical analysis of EAs is, however, far behind. Many researchers thus
have been devoted to understanding the behavior of EAs from a theoretical point of view, which is
still an ongoing challenge.
In the last two decades, a lot of progress has been made on the running time analysis of EAs, which
is one essential theoretical aspect. The running time measures how many objective (i.e., fitness)
function evaluations an EA needs until finding an optimal solution or an approximate solution.
The running time analysis of EAs started with artificial example problems. In [7, 8], a simple singleobjective EA called (1+1)-EA was shown able to solve two well-structured pseudo-Boolean problems
OneMax and LeadingOnes in Θ(n log n) and Θ(n2 ) (where n is the problem size) expected running
time, respectively. These two problems are to maximize the number of 1-bits of a solution and the
number of consecutive 1-bits counting from the left of a solution, respectively. Both of them have
a short path with increasing fitness to the optimum. For some problems (e.g., SPC) where there is
a short path with constant fitness to the optimum, the (1+1)-EA can also find an optimal solution
in polynomial time [19]. But when the problem (e.g., Trap) has a deceptive path (i.e., a path with
increasing fitness away from the optimum), the (1+1)-EA will need exponential running time [15].
More results can refer to [2].
The analysis on simple artificial problems disclosed theoretical properties of EAs (e.g., which problem structures are easy or hard for EAs), and also helped to develop approaches for analyzing more
complex problems. The running time analysis of EAs was then extended to combinatorial optimization problems. For some P-solvable problems, EAs were shown able to find an optimal solution in polynomial time. For example, the minimum spanning tree problem can be solved by
the (1+1)-EA and a simple multi-objective EA called GSEMO in O(m2 (log n + log wmax )) [29] and
O(mn(n + log wmax )) [28] expected time, respectively. Note that m, n and wmax are the number of
edges, the number of nodes and the maximum edge weight of a graph, respectively. For some NPhard problems, EAs were shown able to achieve good approximation ratios in polynomial time. For
example, for the partition problem, the (1+1)-EA can achieve a (4/3)-approximation ratio in O(n2 )
expected time [36]; for the minimum set cover problem, the expected running time of the GSEMO
2

until obtaining a (log m + 1)-approximation ratio is O(m2 n + mn(log n + log cmax )) [11], where m,
n and cmax denote the size of the ground set, the number of subsets and the maximum cost of a
subset, respectively. More running time results of EAs on combinatorial optimization problems can
refer to [30].
For the analysis of the GSEMO (which is a multi-objective EA) on single-objective optimization
problems (e.g., minimum spanning tree and minimum set cover), the original single-objective problem is transformed into a multi-objective problem, which is then solved by the GSEMO. Note that
multi-objective optimization here is just an intermediate process (which might be beneficial [11, 28,
31, 33]), and we still focus on the quality of the best solution w.r.t. the original single-objective problem, in the population found by the GSEMO. Running time analysis of EAs on real multi-objective
optimization problems has also been investigated, where the running time is measured by the number of fitness evaluations until finding the Pareto front (which represents different optimal tradeoffs
between the multiple objectives) or an approximation of the Pareto front. For example, Giel [12]
proved that the GSEMO can solve the bi-objective pseudo-Boolean problem LOTZ in O(n3 ) expected time; for the NP-hard bi-objective minimum spanning tree problem, it was shown that the
GSEMO can obtain a 2-approximation ratio in pseudo-polynomial time [27, 32].
The analysis on combinatorial optimization problems helped to reveal the ability of EAs. However,
most of the previous promising results were obtained for isolated problems, while EAs are known to
be general-purpose optimization algorithms, which can be applied to various problems. Thus, it is
more desirable to provide a general theoretical explanation of the behavior of EAs, that is, to theoretically study the performance of EAs on a general class of combinatorial optimization problems.
To the best of our knowledge, only two pieces of work in this direction have been reported. Reichel
and Skutella [35] first studied the problem class of maximizing linear functions with k matroid constraints, which includes some well-known combinatorial optimization problems such as maximum
matching, Hamiltonian path, etc. They proved that the (1+1)-EA can obtain a (1/k)-approximation
ratio in O(nk+2 (log r + log wmax )) expected running time, where n, r and wmax denote the size of
the ground set, the minimum rank of the ground set w.r.t. one matroid and the maximum weight
of an element, respectively. Later, a generalization of this problem class, i.e., the objective function
is relaxed to satisfy the monotone and submodular property, was considered in [10]. The (1+1)-EA
1
)-approximation ratio in O( 1ǫ n2p(k+1)+1 k log n) expected time,
was shown able to achieve a ( k+1/p+ǫ

where p ≥ 1 and ǫ > 0. Friedrich and Neumann [10] also studied a specific non-monotone case for
the objective function, i.e., the objective function is symmetric. They proved that the expected run1
ning time until the GSEMO obtains a ( (k+2)(1+ǫ)
)-approximation ratio for maximizing symmetric

submodular functions with k matroid constraints is O( 1ǫ nk+6 log n).

3

The aim of this paper is to contribute to this line of research. Considering that the objective function of many combinatorial optimization problems can be non-monotone (not necessarily symmetric) or non-submodular, we study the performance of EAs on these two general problem classes,
maximizing non-monotone submodular functions without constraints and maximizing monotone
non-submodular functions with a size constraint. Note that the objective function is a set function
f : 2V → R which maps a subset of the ground set V to a real value, and a size constraint means that
the size of a subset is not larger than a budget k. We prove that for both problem classes, the GSEMO
can obtain a good approximation guarantee in polynomial expected running time. Our main results
can be summarized as follows.
• For the problem class of maximizing non-monotone submodular functions without constraints,
with special instances including maximum cut [13], maximum facility location [1] and variants
of the maximum satisfiability problem [14], we prove that the GSEMO can achieve a constant
approximation ratio of

1
3

−

ǫ
n

in O( 1ǫ n4 log n) expected running time (i.e., Theorem 1), where n

is the size of the ground set V and ǫ > 0.
• For the problem class of maximizing monotone non-submodular functions with a size constraint, with special instances including sparse regression [6], dictionary selection [21] and
robust influence maximization [5, 16], we prove the approximation guarantee of the GSEMO
w.r.t. each notion of “approximate submodularity”, which measures how close a general set
function f is to submodularity.
(1) In [22], a set function f is ǫ-approximately submodular if the diminishing return property
holds with some deviation ǫ ≥ 0, i.e., for any X ⊆ Y ⊆ V and v ∈
/ Y , f (X ∪ {v}) − f (X) ≥
f (Y ∪{v})−f (Y )−ǫ. f is submodular iff ǫ = 0. We prove that the GSEMO within O(n2 (log n+k))
expected time can find a subset X with f (X) ≥ (1 − e−1 ) · (OP T − kǫ) (i.e., Theorem 2), where
e is the base of the natural logarithm and OP T denotes the optimal function value.
(2) In [6], the approximate submodularity notion of a set function f is characterized by a quantity γ called submodularity ratio. f is submodular iff γ = 1. We prove that the GSEMO within
O(n2 (log n + k)) expected time can find a subset X with f (X) ≥ (1 − e−γ ) · OP T (i.e., Theorem 3).
(3) In [17], a set function f is ǫ-approximately submodular if there exists a submodular set
function g such that ∀X ⊆ V , (1 − ǫ)g(X) ≤ f (X) ≤ (1 + ǫ)g(X). f is submodular iff ǫ = 0.
We prove that the GSEMO within O(n2 (log n + k)) expected time can find a subset X with
f (X) ≥

1
2kǫ
1+ 1−ǫ

1−ǫ k
(1 − e−1 ( 1+ǫ
) ) · OP T (i.e., Theorem 4).

Note that since EAs are general-purpose algorithms which utilize a small amount of problem knowledge, we cannot expect them to beat the best problem-specific algorithm. For the first problem
class, the approximation ratio nearly 1/3 obtained by the GSEMO is worse than the best known one
4

1/2, which was previously obtained by the double greedy algorithm [4]. For the second problem
class, the approximation ratio obtained by the GSEMO w.r.t. each notion of approximate submodularity reaches the best known one, which was previously obtained by the standard greedy algorithm [22, 6, 17]. Particularly, when the objective function is submodular, the obtained approximation ratio by the GSEMO becomes 1 − 1/e, which is optimal in general [25], and also consistent with
the previous result in [10]. Our analytical results on general problem classes together with the previous ones [35, 10] provide a theoretical explanation for the empirically good behaviors of EAs in
diverse applications.
The rest of this paper is organized as follows. Section 2 introduces some preliminaries. The running
time analyses for non-monotone and non-submodular cases are then presented in Sections 3 and 4,
respectively. Section 5 concludes the paper.

2. Preliminaries

In this section, we first introduce the two problem classes studied in this paper, and then introduce
the multi-objective evolutionary algorithm GSEMO and also how to optimize the studied problem
classes by the GSEMO.

2.1. Non-monotone/Non-submodular Function Maximization
Let R and R+ denote the set of reals and non-negative reals, respectively. Given a finite nonempty
set V = {v1 , v2 , . . . , vn }, we study the functions f : 2V → R defined on subsets of V . A set function
f : 2V → R is monotone if for any X ⊆ Y , f (X) ≤ f (Y ). Without loss of generality, we assume that
the monotone function is normalized, i.e., f (∅) = 0. A set function f is submodular [26] if for any
X ⊆ Y ⊆ V and v ∈
/ Y,
f (X ∪ {v}) − f (X) ≥ f (Y ∪ {v}) − f (Y );

(1)

or equivalently for any X ⊆ Y ⊆ V ,
f (Y ) − f (X) ≤

X

v∈Y \X


f (X ∪ {v}) − f (X) .

(2)

We assume that a set function f is given by a value oracle, i.e., for a given subset X, an algorithm
can query an oracle to obtain the value f (X).

5

Our first studied problem class as presented in Definition 1 is to maximize a non-monotone submodular set function. Without loss of generality, we assume that the objective function f is nonnegative. This problem generalizes many NP-hard combinatorial optimization problems including maximum cut [13], maximum facility location [1], variants of the maximum satisfiability problem [14], etc. The best known approximation guarantee is 1/2, which was achieved by the double
greedy algorithm [4].
Definition 1 (Non-monotone Submodular Function Maximization without Constraints)

Given a non-monotone submodular function f : 2V → R+ , it is to find a subset X ⊆ V such that
arg maxX⊆V

f (X).

The second studied problem class is presented in Definition 2. The goal is to find a subset with
at most k elements such that a given monotone non-submodular set function is maximized. This
problem generalizes many NP-hard problems including sparse regression [6], dictionary selection [21]
and robust influence maximization [5, 16], etc. When the objective function is submodular, it was
well known that the standard greedy algorithm achieves the optimal approximation guarantee 1 −
1/e [25, 26]. For non-submodular cases, several notions of “approximate submodularity” [22, 6, 17]
were introduced to measure to what extent a general set function f has the submodular property.
For each approximately submodular notion, the best known approximation guarantee was achieved
by the standard greedy algorithm [22, 6, 17], which iteratively adds one element with the largest f
improvement until k elements are selected.
Definition 2 (Monotone Non-submodular Function Maximization with a Size Constraint)

Given a monotone non-submodular function f : 2V → R+ and a budget k , it is to find a subset
X ⊆ V such that
arg maxX⊆V

f (X) s.t. |X| ≤ k.

In [22], the approximate submodularity as presented in Definition 3 was defined based on the diminishing return property (i.e., Eq. (1)). That is, the approximately submodular degree depends
on how large a deviation of ǫ the diminishing return property can hold with. It is easy to see that
f is submodular iff ǫ = 0. The standard greedy algorithm was proved to find a subset X with
f (X) ≥ (1 − e−1 ) · (OP T − kǫ) [22], where OP T denotes the optimal function value.
Definition 3 (ǫ-Approximately Submodular [22])

Let ǫ ≥ 0. A set function f : 2V → R is ǫ-approximately submodular if for any X ⊆ Y ⊆ V and v ∈
/ Y,
f (X ∪ {v}) − f (X) ≥ f (Y ∪ {v}) − f (Y ) − ǫ.
In [6], the submodularity ratio as presented in Definition 4 was introduced to measure the closeness
of a set function f to submodularity. It is easy to see from Eq. (2) that f is submodular iff γU,k (f ) = 1
6

for any U and k. When f is clear in the paper, we will use γU,k shortly. The standard greedy algorithm
was proved to find a subset X with f (X) ≥ (1 − e−γX,k ) · OP T [6].
Definition 4 (Submodularity Ratio [6])

Let f : 2V → R be a set function. The submodularity ratio of f with respect to a set U ⊆ V and a
parameter k ≥ 1 is
γU,k (f ) =

min

L⊆U,S:|S|≤k,S∩U=∅

P

∪ {v}) − f (L))
.
f (L ∪ S) − f (L)

v∈S (f (L

The above two notions of approximate submodularity are based on the equivalent statements Eqs. (1)
and (2) of submodularity, while in [17], the approximate submodularity of a set function f as presented in Definition 5 was defined based on the closeness to other submodular functions. It is easy
to see that f is submodular iff ǫ = 0. The standard greedy algorithm was proved to find a subset X
with f (X) ≥

1
4kǫ
1+ (1−ǫ)
2

2k
(1 − e−1 ( 1−ǫ
1+ǫ ) ) · OP T [17].

Definition 5 (ǫ-Approximately Submodular [17])

Let ǫ ≥ 0. A set function f : 2V → R is ǫ-approximately submodular if there exists a submodular set
function g such that ∀X ⊆ V ,
(1 − ǫ) · g(X) ≤ f (X) ≤ (1 + ǫ) · g(X).

2.2. Multi-objective Evolutionary Algorithms
To investigate the performance of EAs optimizing the two problem classes in Definitions 1 and 2,
we consider a simple multi-objective EA called GSEMO, which has been widely used in previous
theoretical analyses [11, 31, 32, 37]. The GSEMO as presented in Algorithm 1 is used for maximizing
multi-objective pseudo-Boolean problems with m objective functions fi : {0, 1}n → R (1 ≤ i ≤ m).
Note that a pseudo-Boolean function f : {0, 1}n → R naturally characterizes a set function f : 2V →
R, since a subset X of V can be naturally represented by a Boolean vector x ∈ {0, 1}n, where the
i-th bit xi = 1 means that vi ∈ X, and xi = 0 means that vi ∈
/ X. Throughout the paper, we will not
distinguish x ∈ {0, 1}n and its corresponding subset for notational convenience.
Before introducing the GSEMO, we first introduce some basic concepts in multi-objective maximization. Since the objectives to be maximized are usually conflicted, there is no canonical complete order on the solution space. The comparison between two solutions relies on the domination
relationship. For two solutions x and x′ , x weakly dominates x′ (i.e., x is better than x′ , denoted by
x  x′ ) if ∀1 ≤ i ≤ m, fi (x) ≥ fi (x′ ); x dominates x′ (i.e., x is strictly better than x′ , denoted by
x ≻ x′ ) if x  x′ and fi (x) > fi (x′ ) for some i. The domination relationship between two solutions
x and x′ can be formally stated as follows:
7

Algorithm 1 GSEMO Algorithm
Given m pseudo-Boolean objective functions f1 , f2 , . . . , fm , where fi : {0, 1}n → R, the GSEMO
consists of the following steps:
1:

Choose x ∈ {0, 1}n uniformly at random

2:

P ← {x}

3:

repeat

4:

Choose x from P uniformly at random

5:

Create x′ by flipping each bit of x with probability 1/n

6:

Create x′′ ← V \ x′

7:

for y ∈ {x′, x′′ }

8:
9:
10:
11:
12:

if ∄z ∈ P such that z ≻ y
P ← (P \ {z ∈ P | y  z}) ∪ {y}
end if
end for
until some criterion is met
• x  x′ if ∀1 ≤ i ≤ m, fi (x) ≥ fi (x′ );
• x ≻ x′ if x  x′ and fi (x) > fi (x′ ) for some i.

But if neither x is better than x′ nor x′ is better than x, we say that they are incomparable. A solution
is Pareto optimal if there is no other solution that dominates it. The set of objective vectors of all the
Pareto optimal solutions constitutes the Pareto front. The goal of multi-objective optimization is to
find the Pareto front, that is, to find at least one corresponding solution for each objective vector in
the Pareto front.
The procedure of the GSEMO algorithm is presented in Algorithm 1. Starting from a random solution (lines 1-2), it iteratively tries to improve the quality of the solutions in the population P (lines 312). In each iteration, a new solution x′ is generated by randomly flipping bits of an archived solution x selected from the current population P (lines 4-5); the complementary set x′′ = V \ x′ of x′ is
also generated (line 6); these two newly generated solutions are then used to update the population
P (lines 7-11). In the updating procedure, if y ∈ {x′ , x′′ } is not dominated by (i.e., not strictly worse
than) any previously archived solution (line 8), it will be added into P , and meanwhile those previously archived solutions weakly dominated by (i.e., worse than) y will be removed from P (line 9).
It is easy to see that the population P will always contain a set of incomparable solutions due to
the domination-based comparison. Note that the GSEMO here is a little different from its original
version [11, 31, 32]. In the original GSEMO algorithm, only x′ is generated and used to update the
population in each iteration, while here we also generate the complementary set of x′ and use both
8

of them to update the population.
For optimizing the two problems in Definitions 1 and 2 by the GSEMO, each problem is transformed
into a bi-objective maximization problem
arg maxx∈{0,1}n

(f1 (x), f2 (x)),

where f1 (x) = f (x) and f2 (x) = −|x|. That is, the GSEMO is to maximize the objective function
Pn
f and minimize the subset size |x| simultaneously. Note that |x| = i=1 xi denotes the number of

1-bits of a solution x. When the GSEMO terminates after running a number of iterations, the best
solution w.r.t. the original single-objective problem in the resulting population P will be returned.
For the first problem in Definition 1, the solution with the largest f value in P (i.e., arg maxx∈P f (x))

will be returned. For the second problem in Definition 2, the solution with the largest f value satisfying the size constraint in P (i.e., arg maxx∈P,|x|≤k f (x)) will be returned. The running time of the
GSEMO is measured by the number of fitness evaluations until the best solution w.r.t. the original single-objective problem in the population reaches some approximation guarantee for the first
time. Since only the new solutions x′ and x′′ need to be evaluated in each iteration of the GSEMO,
the number of fitness evaluations is just the double of the number of iterations of the GSEMO.
Note that multi-objective optimization here is just an intermediate process, which has been shown
helpful for solving some single-objective combinatorial optimization problems [11, 28, 31, 33]. We
still focus on the quality of the best solution w.r.t. the original single-objective problem, in the population found by the GSEMO, rather than the quality of the population w.r.t. the transformed multiobjective optimization problem.

3. Non-monotone Submodular Function Maximization without Constraints

In this section, we theoretically analyze the performance of the GSEMO for maximizing non-monotone
submodular functions without constraints. We prove in Theorem 1 that the GSEMO can achieve a
constant approximation ratio of nearly 1/3 in polynomial time. Note that OP T denotes the optimal
function value. Inspired from the proof of Theorem 4 in [10], our proof idea is to follow the behavior
of the local search algorithm [9], which iteratively tries to improve a solution by inserting or deleting one element. The proof relies on Lemma 1, which shows that it is always possible to improve a
solution until a good approximation has been achieved. This lemma is extracted from Lemma 3.4
in [9].
Lemma 1

[9] Let x ∈ {0, 1}n be a solution such that no solution x′ with the objective value f (x′ ) > (1+ nǫ2 )·f (x)
9

can be achieved by inserting one element into x or deleting one element from x, where ǫ > 0. Then
max{f (x), f (V \ x)} ≥ ( 13 − nǫ ) · OP T .
Theorem 1

For maximizing a non-monotone submodular function without constraints, the expected running
time of the GSEMO until finding a solution x with f (x) ≥ ( 31 − nǫ ) · OP T is O( 1ǫ n4 log n), where ǫ > 0.
Proof. We divide the optimization process into three phases: (1) starts from an initial random solution and finishes until finding the special solution {0}n (i.e., ∅); (2) starts after phase (1) and finishes
until finding a solution with the objective value at least OP T /n; (3) starts after phase (2) and finishes until finding a solution with the desired approximation guarantee. We analyze the expected
running time of each phase, respectively, and then sum up them to get an upper bound on the total
expected running time of the GSEMO.
For phase (1), we consider the minimum number of 1-bits of the solutions in the population P ,
denoted by Jmin . That is, Jmin = min{|x| | x ∈ P }. Assume that currently Jmin = i > 0, and let
x be the corresponding solution, i.e., |x| = i. It is easy to see that Jmin cannot increase because
x cannot be weakly dominated by a solution with more 1-bits. In each iteration of the GSEMO, to
decrease Jmin , it is sufficient to select x in line 4 of Algorithm 1 and flipping only one 1-bit of x in
line 5. This is because the newly generated solution x′ now has the smallest number of 1-bits (i.e.,
|x′ | = i−1) and no solution in P can dominate it; thus it will be included into P . Let Pmax denote the
largest size of P during the run of the GSEMO. The probability of selecting x in line 4 of Algorithm 1
is

1
|P |

i
n (1

≥

−

1
Pmax

1 n−1
n)

due to uniform selection, and the probability of flipping only one 1-bit of x in line 5 is
≥

i
en ,

since x has i 1-bits. Thus, the probability of deceasing Jmin by at least 1 in each

iteration of the GSEMO is at least

i
enPmax .

Note that Jmin ≤ n. We can then get that the expected

number of iterations of phase (1) (i.e., Jmin reaches 0) is at most
n
X
enPmax
i=1

i

= O(nPmax log n).

Note that the solution {0}n will be always kept in P once generated, since it has the smallest subset
size 0 and no other solution can weakly dominate it.
For phase (2), it is sufficient that in one iteration of the GSEMO, the solution {0}n is selected in line 4,
and only a specific 0-bit corresponding to the best single element v ∗ (i.e., v ∗ ∈ arg maxv∈V f ({v})) is
flipped in line 5. That is, the solution {v ∗ } is generated. Since the objective function f is submodular
and non-negative, we easily have f ({v ∗ }) ≥ OP T /n. After generating the solution {v ∗ }, it will then
be used to update the population P , which makes P always contain a solution z weakly dominating
{v ∗ }, i.e., f (z) ≥ f ({v ∗ }) ≥ OP T /n and |z| ≤ |{v ∗ }| = 1. Thus, we only need to analyze the expected number of iterations of the GSEMO until generating the solution {v ∗ }. Since the probability
10

of selecting {0}n in line 4 of the GSEMO is at least
0-bit in line 5 is

1
n (1

−

1 n−1
n)

≥

1
en ,

1
Pmax

and the probability of flipping only a specific

the expected number of iterations of phase (2) is O(nPmax ).

As in [9], we call a solution x a (1+α)-approximate local optimum if f (x\{v}) ≤ (1+α)·f (x) for any
v ∈ x and f (x ∪ {v}) ≤ (1 + α) · f (x) for any v ∈
/ x. According to Lemma 1, we know that a (1 +

ǫ
n2 )-

approximate local optimum x satisfies that max{f (x), f (V \ x)} ≥ ( 31 − nǫ ) · OP T . For phase (3), we
thus only need to analyze the expected number of iterations until generating a (1+ nǫ2 )-approximate
local optimum x′ in line 5 of Algorithm 1. This is because both x′ and V \ x′ will be used to update
the population P , and then for either one of x′ and V \ x′ , P will always contain one solution weakly
dominating it, which implies that max{f (x) | x ∈ P } ≥ max{f (x′ ), f (V \ x′ )} ≥ ( 13 −

ǫ
n)

· OP T .

We then consider the largest f value of the solutions in the population P , denoted by Jmax . That is,
Jmax = max{f (x) | x ∈ P }. After phase (2), Jmax ≥ OP T /n, and let x be the corresponding solution,
i.e., f (x) = Jmax . It is obvious that Jmax cannot decrease, because x cannot be weakly dominated by
a solution with a smaller f value. As long as x is not a (1 + nǫ2 )-approximate local optimum, we know
that a new solution x′ with f (x′ ) > (1 +

ǫ
n2 )f (x)

= (1 + nǫ2 )Jmax can be generated through selecting

x in line 4 of Algorithm 1 and flipping only one specific 1-bit (i.e., deleting one specific element from
x) or one specific 0-bit (i.e., adding one specific element into x) in line 5, the probability of which is
at least

1
Pmax

· n1 (1 − n1 )n−1 ≥

1
enPmax .

Since x′ now has the largest f value and no other solution in

P can dominate it, it will be included into P . Thus, Jmax can increase by at least a factor of 1 +
with probability at least

1
enPmax

ǫ
n2

in each iteration. Such an increase on Jmax is called a successful step.

Thus, a successful step needs at most enPmax expected number of iterations. It is also easy to see
that until generating a (1 +
most log1+

ǫ
n2

OP T
OP T /n

ǫ
n2 )-approximate

local optimum, the number of successful steps is at

= O( 1ǫ n2 log n). Thus, the expected number of iterations of phase (3) is at most
enPmax · O



1 2
n log n
ǫ



=O




1 3
n Pmax log n .
ǫ

From the procedure of the GSEMO, we know that the solutions maintained in P must be incomparable. Thus, each value of one objective can correspond to at most one solution in P . Because the
second objective f2 (x) = −|x| can only belong to {0, −1, . . . , −n}, we have Pmax ≤ n + 1. Hence,
the expected running time of the GSEMO for finding a solution with the objective function value at
least ( 13 − nǫ ) · OP T is
O(nPmax log n) + O(nPmax ) + O



1 3
n Pmax log n
ǫ

11



=O




1 4
n log n .
ǫ

4. Monotone Non-submodular Function Maximization with a Size Constraint

In this section, we analyze the performance of the GSEMO for maximizing monotone non-submodular
functions with a size constraint. We prove the polynomial-time approximation guarantee of the
GSEMO w.r.t. each notion of approximate submodularity (i.e., Definitions 3-5), respectively. Theorem 2 gives the approximation guarantee of the GSEMO w.r.t. the ǫ-approximately submodular
notion in Definition 3, where OP T denotes the optimal function value. Note that this approximation guarantee obtained by the GSEMO reaches the best known one, which was previously obtained
by the standard greedy algorithm [22]. Inspired from the proof of Theorem 2 in [10], our proof idea is
to follow the behavior of the standard greedy algorithm, which iteratively adds one element with the
currently largest improvement on f . The proof relies on the property of f in Lemma 2, that for any
x ∈ {0, 1}n , there always exists another element, the inclusion of which can bring an improvement
on f roughly proportional to the current distance to the optimum.
Lemma 2

Assume that a set function f is monotone and ǫ-approximately submodular as in Definition 3. Then,
/ x such that
for any x ∈ {0, 1}n, there exists one element v ∈
f (x ∪ {v}) − f (x) ≥

1
(OP T − f (x)) − ǫ.
k

Proof. Let x∗ be an optimal solution, i.e., f (x∗ ) = OP T . We denote the elements in x∗ \ x by
v1∗ , v2∗ , . . . , vl∗ , where |x∗ \ x| = l ≤ k. Then, we have
f (x∗ ) − f (x) ≤ f (x ∪ x∗ ) − f (x)
=

l
X
j=1

≤

l
X
j=1


∗
f (x ∪ {v1∗ , . . . , vj∗ }) − f (x ∪ {v1∗ , . . . , vj−1
})

f (x ∪ {vj∗ }) − f (x) + ǫ ,

where the first inequality is by the monotonicity of f , and the last inequality is derived by Definition 3 since f is ǫ-approximately submodular. Let v ∗ = arg maxv∈x∗ \x f (x ∪ {v}). Then, we have
f (x ∪ {v ∗ }) − f (x) ≥

1
1
(f (x∗ ) − f (x)) − ǫ ≥ (OP T − f (x)) − ǫ.
l
k

Theorem 2

For maximizing a monotone non-submodular function f with a size constraint, where f is ǫ-approximately
submodular as in Definition 3, the expected running time of the GSEMO until finding a solution x
with |x| ≤ k and f (x) ≥ (1 − e−1 ) · (OP T − kǫ) is O(n2 (log n + k)).
12

Proof. We divide the optimization process into two phases: (1) starts from an initial random solution and finishes until finding the special solution {0}n ; (2) starts after phase (1) and finishes until
finding a solution with the desired approximation guarantee. As the analysis of phase (1) in the proof
of Theorem 1, we know that the population P will contain the solution {0}n after O(nPmax log n) iterations in expectation.
For phase (2), we consider a quantity Jmax , which is defined as
(

Jmax = max j ∈ [0, k] | ∃x ∈ P, |x| ≤ j ∧ f (x) ≥

1
1− 1−
k

j !

)

· (OP T − kǫ) .

That is, Jmax denotes the maximum value of j ∈ [0, k] such that in the population P , there exists a
solution x with |x| ≤ j and f (x) ≥ (1 − (1 − k1 )j ) · (OP T − kǫ). We analyze the expected number of
iterations until Jmax = k, which implies that there exists one solution x in P satisfying that |x| ≤ k
and f (x) ≥ (1 − (1 − k1 )k ) · (OP T − kǫ) ≥ (1 − e−1 ) · (OP T − kǫ). That is, the desired approximation
guarantee is reached.
The current value of Jmax is at least 0, since the population P contains the solution {0}n , which will
always be kept in P once generated. Assume that currently Jmax = i < k. Let x be a corresponding
solution with the value i, i.e., |x| ≤ i and f (x) ≥ (1 − (1 − k1 )i ) · (OP T − kǫ). It is easy to see that
Jmax cannot decrease because cleaning x from P (line 9 of Algorithm 1) implies that x is weakly
dominated by a newly generated solution y, which must satisfy that |y| ≤ |x| and f (y) ≥ f (x). By
Lemma 2, we know that flipping one specific 0 bit of x (i.e., adding a specific element) can generate
a new solution x′ , which satisfies that f (x′ ) − f (x) ≥ k1 (OP T − f (x)) − ǫ. Then, we have


i+1 !

1
1
1
′
f (x ) ≥ 1 −
f (x) + · OP T − ǫ ≥ 1 − 1 −
· (OP T − kǫ),
k
k
k
where the last inequality is derived by f (x) ≥ (1−(1− k1 )i )·(OP T −kǫ). Since |x′ | = |x|+1 ≤ i+1, x′
will be included into P ; otherwise, x′ must be dominated by one solution in P (line 8 of Algorithm 1),
and this implies that Jmax has already been larger than i, which contradicts with the assumption
Jmax = i. After including x′ , Jmax ≥ i + 1. Thus, Jmax can increase by at least 1 in one iteration with
probability at least

1
Pmax

· n1 (1 − n1 )n−1 ≥

selecting x in line 4 of Algorithm 1 and

1
enPmax ,

1
n (1

where

1
Pmax

is a lower bound on the probability of

− n1 )n−1 is the probability of flipping a specific bit of x

while keeping other bits unchanged in line 5. Then, it needs at most enPmax expected number of
iterations to increase Jmax . Thus, after at most k · enPmax iterations in expectation, Jmax must have
reached k.
As the proof of Theorem 1, we know that Pmax ≤ n + 1. Thus, by summing up the expected running
time of two phases, we get that the expected running time of the GSEMO for finding a solution x
with |x| ≤ k and f (x) ≥ (1 − e−1 ) · (OP T − kǫ) is O(nPmax log n + knPmax ) = O(n2 (log n + k)).
13

Theorem 3 gives the approximation guarantee of the GSEMO w.r.t. the submodularity ratio in Definition 4. Note that it was proved that the standard greedy algorithm can find a subset x with |x| = k
and f (x) ≥ (1 − e−γx,k ) · OP T [6]. Thus, Theorem 3 shows that the GSEMO can achieve nearly this
best known approximation guarantee. The proof of Theorem 3 is similar to that of Theorem 2. The
main difference is that a different inductive inequality on f is used in the definition of the quantity
Jmax , due to the change of the adopted notion of approximate submodularity. For concise illustration, we will mainly show the difference in the proof of Theorem 3.
Lemma 3

[34] Assume that a set function f is monotone and non-submodular. Then, for any x ∈ {0, 1}n, there
/ x such that
exists one element v ∈
f (x ∪ {v}) − f (x) ≥

γx,k
(OP T − f (x)),
k

where γx,k is the submodularity ratio of f w.r.t. x and k as in Definition 4.
Theorem 3

For maximizing a monotone non-submodular function f with a size constraint, the expected running time of the GSEMO until finding a solution x with |x| ≤ k and f (x) ≥ (1 − e−γmin ) · OP T is
O(n2 (log n + k)), where γmin = minx:|x|=k−1 γx,k and γx,k is the submodularity ratio of f w.r.t. x and
k as in Definition 4.

Proof. The proof is similar to that of Theorem 2. We use a different Jmax , which is defined as





γmin j
· OP T .
Jmax = max j ∈ [0, k] | ∃x ∈ P, |x| ≤ j ∧ f (x) ≥ 1 − 1 −
k
It is easy to verify that Jmax = k implies that the desired approximation guarantee is reached, since
there must exist one solution x in P satisfying that |x| ≤ k and f (x) ≥ (1 − (1 −
(1 − e

−γmin

γmin k
k ) )

· OP T ≥

) · OP T . Assume that currently Jmax = i < k and x is a corresponding solution, i.e.,

|x| ≤ i and f (x) ≥ (1 − (1 −

γmin i
k ) )

· OP T . We then only need to show that flipping one specific

0 bit of x can generate a new solution x′ with f (x′ ) ≥ (1 − (1 −

γmin i+1
)
k )

· OP T . By Lemma 3,

we know that flipping one specific 0 bit of x can generate a new solution x′ , which satisfies that
γx,k
k (OP T

− f (x)). Then, we have




γx,k 
γx,k
γmin i
γx,k  
f (x′ ) ≥ 1 −
f (x) +
1−
· OP T
· OP T ≥ 1 − 1 −
k
k
k
k



γmin i+1
· OP T,
≥ 1− 1−
k

f (x′ ) − f (x) ≥

where the second inequality is by f (x) ≥ (1 − (1 −

γmin i
k ) )

· OP T , and the last inequality is by γx,k ≥

γmin , which can be easily derived from |x| < k and γx,k decreasing with x. Thus, the theorem holds.

14

Theorem 4 gives the approximation guarantee of the GSEMO w.r.t. the ǫ-approximately submodular
ratio in Definition 5. Note that the standard greedy algorithm obtains the best known approximation
guarantee f (x) ≥

1
4kǫ
1+ (1−ǫ)
2

2k
(1 − (1 − k1 )k ( 1−ǫ
1+ǫ ) ) · OP T [17]. Comparing with this, the approximation

guarantee of the GSEMO is slightly better, since

k 
k !

i
k−1
X 
1
1
1 1−ǫ
1−ǫ
1−ǫ
1
−
1
−
1
−
=
·
2kǫ
k
1+ǫ
k(1 + ǫ) i=0
k 1+ǫ
1 + 1−ǫ
!
i


2
k 
2k !
k−1 
1
1
1−ǫ
1
1−ǫ
(1 − ǫ)2 X
1−
1− 1−
.
=
·
≥
4kǫ
k(1 + ǫ)2 i=0
k
1+ǫ
k
1+ǫ
1 + (1−ǫ)
2
The proof of Theorem 4 is also similar to that of Theorem 2, except that a different inductive inequality on f is used in the definition of the quantity Jmax , due to the change of the adopted notion
of approximate submodularity.
Lemma 4

Assume that a set function f is monotone and ǫ-approximately submodular as in Definition 5. Then,
/ x such that
for any x ∈ {0, 1}n, there exists one element v ∈
1−ǫ
1−ǫ
f (x) ≥
(OP T − f (x)).
1+ǫ
k(1 + ǫ)

f (x ∪ {v}) −

Proof. Let x∗ be an optimal solution, i.e., f (x∗ ) = OP T . Let v ∗ = arg maxv∈x∗ \x f (x∪{v}). Since f is
ǫ-approximately submodular as in Definition 5, we use g to denote one corresponding submodular
function satisfying that for all x ∈ {0, 1}n, (1 − ǫ)g(x) ≤ f (x) ≤ (1 + ǫ)g(x). Then, we have
g(x∗ ∪ x) − g(x) ≤

X

v∈x∗ \x


g(x ∪ {v}) − g(x)


X  1
≤
f (x ∪ {v}) − g(x)
1−ǫ
v∈x∗ \x


1
f (x ∪ {v ∗ }) − g(x) ,
≤k
1−ǫ
where the first inequality is by the submodularity of g (i.e., Eq. (2)), the second inequality is by (1 −
ǫ)g(x) ≤ f (x) for any x, and the last inequality is by the definition of v ∗ and |x∗ | ≤ k. By reordering
the terms, we get


1
1−ǫ
∗
(1 − ǫ)g(x).
g(x ∪ x) + 1 −
f (x ∪ {v }) ≥
k
k
∗

Since g(x) ≥

1
∗
1+ǫ f (x) and g(x ∪x)

≥

1
∗
1+ǫ f (x ∪x)

≥

1
∗
1+ǫ f (x )

=

1
1+ǫ OP T

(where the last inequality

is by the monotonicity of f ), we have
f (x ∪ {v ∗ }) ≥



1−ǫ
1 1−ǫ
OP T + 1 −
f (x).
k(1 + ǫ)
k 1+ǫ

By reordering the terms, the lemma holds.

15

Theorem 4

For maximizing a monotone non-submodular function f with a size constraint, where f is ǫ-approximately
submodular as in Definition 5, the expected running time of the GSEMO until finding a solution
x with |x| ≤ k and f (x) ≥

1
2kǫ
1+ 1−ǫ

(1 − (1 −

1 k 1−ǫ k
k ) ( 1+ǫ ) )

· OP T ≥

1
2kǫ
1+ 1−ǫ

k
(1 − e−1 ( 1−ǫ
1+ǫ ) ) · OP T is

O(n2 (log n + k)).

Proof. The proof is similar to that of Theorem 2. We use a different Jmax , which is defined as
(
)
j 
j !

1
1−ǫ
1
Jmax = max j ∈ [0, k] | ∃x ∈ P, |x| ≤ j ∧ f (x) ≥
· OP T .
1− 1−
2kǫ
k
1+ǫ
1 + 1−ǫ
It is easy to verify that Jmax = k implies that the desired approximation guarantee is reached. Assume that currently Jmax = i < k and x is a corresponding solution, i.e., |x| ≤ i and f (x) ≥
1
2kǫ
1+ 1−ǫ

1−ǫ i
) ) · OP T . We then only need to show that flipping one specific 0 bit of x
(1 − (1 − k1 )i ( 1+ǫ

can generate a new solution x′ with f (x′ ) ≥

1
2kǫ
1+ 1−ǫ

i+1
) · OP T . By Lemma 4,
(1 − (1 − k1 )i+1 ( 1−ǫ
1+ǫ )

we know that flipping one specific 0 bit of x can generate a new solution x′ , which satisfies that
f (x′ ) −

1−ǫ
1+ǫ f (x)

f (x′ ) ≥
≥



≥

1−

1−ǫ
k(1+ǫ) (OP T

1
k



1
2kǫ
1 + 1−ǫ

− f (x)). Then, we have

1−ǫ
1−ǫ
f (x) +
· OP T
1+ǫ
k(1 + ǫ)

i+1 
i+1 !
1
1−ǫ
1− 1−
· OP T,
k
1+ǫ

where the last inequality is by f (x) ≥

1
2kǫ
1+ 1−ǫ

1−ǫ i
(1 − (1 − k1 )i ( 1+ǫ
) ) · OP T . Thus, the theorem holds.

Thus, we have shown that for each notion of approximate submodularity, the GSEMO can always
obtain the best known approximation guarantee. Particularly, when the objective function is submodular, the quantity characterizing the approximately submodular degree in Definitions 3-5 becomes ǫ = 0, γU,k = 1 and ǫ = 0, respectively; thus the approximation guarantees obtained by the
GSEMO in Theorems 2-4 all become 1 − 1/e, which is optimal in general [25], and also consistent
with the previous result in [10].

5. Conclusion

This paper theoretically studies the approximation performance of EAs for two general classes of
combinatorial optimization problems, maximizing non-monotone submodular functions without
constraints and maximizing monotone non-submodular functions with a size constraint. We prove
that in polynomial expected running time, a simple multi-objective EA called GSEMO can achieve
a constant approximation guarantee of nearly 1/3 for the first problem class, and can achieve the
16

best known approximation guarantee for the second problem class. These results together with the
previous ones for the problem class of maximizing monotone submodular functions with matroid
constraints [10, 35] provide a theoretical explanation for the empirically good performance of EAs
in various applications. A question that will be investigated in the future is to investigate whether
simple single-objective EAs such as the (1+1)-EA can achieve good approximation guarantees on the
studied two problem classes. Most of the existing studies considered the problems where the objective function is a set function. We will also try to investigate the performance of EAs for optimizing
functions over the integer lattice or continuous domains.

References
[1] A. A. Ageev and M. I. Sviridenko. An 0.828-approximation algorithm for the uncapacitated
facility location problem. Discrete Applied Mathematics, 93(2):149–156, 1999.
[2] A. Auger and B. Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific, Singapore, 2011.
[3] T. Bäck. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary
Programming, Genetic Algorithms. Oxford University Press, Oxford, UK, 1996.
[4] N. Buchbinder, M. Feldman, J. Seffi, and R. Schwartz. A tight linear time (1/2)-approximation
for unconstrained submodular maximization. SIAM Journal on Computing, 44(5):1384–1402,
2015.
[5] W. Chen, T. Lin, Z. Tan, M. Zhao, and X. Zhou. Robust influence maximization. In Proceedings
of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
(KDD’16), pages 795–804, San Francisco, CA, 2016.
[6] A. Das and D. Kempe. Submodular meets spectral: Greedy algorithms for subset selection,
sparse approximation and dictionary selection. In Proceedings of the 28th International Conference on Machine Learning (ICML’11), pages 1057–1064, Bellevue, WA, 2011.
[7] S. Droste, T. Jansen, and I. Wegener. A rigorous complexity analysis of the (1+1) evolutionary
algorithm for separable functions with Boolean inputs. Evolutionary Computation, 6(2):185–
196, 1998.
[8] S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276(1-2):51–81, 2002.
[9] U. Feige, V. S. Mirrokni, and J. Vondrak. Maximizing non-monotone submodular functions.
SIAM Journal on Computing, 40(4):1133–1153, 2011.
17

[10] T. Friedrich and F. Neumann. Maximizing submodular functions under matroid constraints by
evolutionary algorithms. Evolutionary Computation, 23(4):543–558, 2015.
[11] T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt. Approximating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation, 18(4):617–633, 2010.
[12] O. Giel. Expected runtimes of a simple multi-objective evolutionary algorithm. In Proceedings
of the 2003 IEEE Congress on Evolutionary Computation (CEC’03), pages 1918–1925, Canberra,
Australia, 2003.
[13] M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut
and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115–
1145, 1995.
[14] J. Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798–859, 2001.
[15] J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127(1):57–85, 2001.
[16] X. He and D. Kempe. Robust influence maximization. In Proceedings of the 22nd ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining (KDD’16), pages 885–894,
San Francisco, CA, 2016.
[17] T. Horel and Y. Singer. Maximization of approximately submodular functions. In Advances In
Neural Information Processing Systems 29 (NIPS’16), pages 3045–3053, Barcelona, Spain, 2016.
[18] G. S. Hornby, A. Globus, D. S. Linden, and J. D. Lohn. Automated antenna design with evolutionary algorithms. In Proceedings of the 2006 American Institute of Aeronautics and Astronautics Conference on Space, pages 19–21, San Jose, CA, 2006.
[19] T. Jansen and I. Wegener. Evolutionary algorithms-how to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Transactions on Evolutionary Computation, 5(6):589–599, 2001.
[20] J. R. Koza, M. A. Keane, and M. J. Streeter. What’s AI done for me lately? Genetic programming’s
human-competitive results. IEEE Intelligent Systems, 18(3):25–31, 2003.
[21] A. Krause and V. Cevher. Submodular dictionary selection for sparse representation. In Proceedings of the 27th International Conference on Machine Learning (ICML’10), pages 567–574,
Haifa, Israel, 2010.

18

[22] A. Krause, A. Singh, and C. Guestrin. Near-optimal sensor placements in Gaussian processes:
Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9:
235–284, 2008.
[23] P. C. Ma, K. C. Chan, X. Yao, and D. K. Chiu. An evolutionary clustering algorithm for gene
expression microarray data analysis. IEEE Transactions on Evolutionary Computation, 10(3):
296–314, 2006.
[24] A. Mukhopadhyay, U. Maulik, S. Bandyopadhyay, and C. A. C. Coello. A survey of multiobjective
evolutionary algorithms for data mining: Part I. IEEE Transactions on Evolutionary Computation, 18(1):4–19, 2014.
[25] G. L. Nemhauser and L. A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3(3):177–188, 1978.
[26] 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.
[27] F. Neumann. Expected runtimes of a simple evolutionary algorithm for the multi-objective
minimum spanning tree problem. European Journal of Operational Research, 181(3):1620–
1629, 2007.
[28] F. Neumann and I. Wegener. Minimum spanning trees made easier via multi-objective optimization. Natural Computing, 5(3):305–319, 2006.
[29] F. Neumann and I. Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science, 378(1):32–40, 2007.
[30] F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization: Algorithms
and Their Computational Complexity. Springer-Verlag, Berlin, Germany, 2010.
[31] F. Neumann, J. Reichel, and M. Skutella. Computing minimum cuts by randomized search
heuristics. Algorithmica, 59(3):323–342, 2011.
[32] C. Qian, Y. Yu, and Z.-H. Zhou. An analysis on recombination in multi-objective evolutionary
optimization. Artificial Intelligence, 204:99–119, 2013.
[33] C. Qian, Y. Yu, and Z.-H. Zhou. On constrained Boolean Pareto optimization. In Proceedings
of the 24th International Joint Conference on Artificial Intelligence (IJCAI’15), pages 389–395,
Buenos Aires, Argentina, 2015.
[34] C. Qian, J.-C. Shi, Y. Yu, K. Tang, and Z.-H. Zhou. Parallel Pareto optimization for subset selection. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI’16), pages 1939–1945, New York, NY, 2016.
19

[35] J. Reichel and M. Skutella. Evolutionary algorithms and matroid optimization problems. Algorithmica, 57(1):187–206, 2010.
[36] C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science
(STACS’05), pages 44–56, Stuttgart, Germany, 2005.
[37] Y. Yu, X. Yao, and Z.-H. Zhou. On the approximation ability of evolutionary optimization with
application to minimum set cover. Artificial Intelligence, 180:20–33, 2012.

20

