Winter 2015, Vol. 23, No. 4, Pages 543-558
Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms
Many combinatorial optimization problems have underlying goal functions that are submodular. The classical goal is to find a good solution for a given submodular function f under a given set of constraints. In this paper, we investigate the runtime of a simple single objective evolutionary algorithm called (1+1) EA and a multiobjective evolutionary algorithm called GSEMO until they have obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints, we show that the GSEMO achieves a (1-1/e)-approximation in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of k ≥ 2 matroids, we show that the (1 +1) EA achieves a (1/k + δ)-approximation in expected polynomial time for any constant δ > 0. Turning to nonmonotone symmetric submodular functions with k ≥ 1 matroid intersection constraints, we show that the GSEMO achieves a 1/((k+2)(1+ε))-approximation in expected time .