Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization

Many combinatorial optimization problems that face diminishing returns can be stated in terms of a submodular function under given set of constraints [7]. The maximization of a non-monotone submodular function even without constraints includes the classical maximum cut problem in graphs and is therefore an NP-hard combinatorial optimization problem that cannot be solved in polynomial time unless P = N P but different types of approximation algorithms are available [2]. Monotone submodular functions play a special role in the area of optimization as they capture import coverage and influence maximization problems in networks. The maximization of monotone submodular functions is NP-hard even for the case of simple constraint that limits the number of elements that can be chosen, but greedy algorithms have shown to obtain best possible approximation guarantees for different types of constraints [7, 8]. At best, one can hope to develop a method that can provide an α-approximation in polynomial time, i.e., a solution with a value of at least α f(x