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 under a given set of constraints. In this paper, we investigate the runtime of a simple single objective evolutionary algorithm called () 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 -approximation in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of matroids, we show that the () EA achieves a ()-approximation in expected polynomial time for any constant . Turning to nonmonotone symmetric submodular functions with  matroid intersection constraints, we show that the GSEMO achieves a -approximation in expected time .