title: Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms.
abstract: 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 O(n(k + 6)log(n)/ε.
authors.affiliation: Hasso Plattner Institute, Potsdam, Germany friedrich@hpi.de.
authors.forename: Tobias
authors.initials: T
authors.lastname: Friedrich
authors.affiliation: School of Computer Science, University of Adelaide, Australia frank.neumann@adelaide.edu.au.
authors.forename: Frank
authors.initials: F
authors.lastname: Neumann
mesh_terms: D000465:Algorithms; D005075:Biological Evolution; D019295:Computational Biology; D003198:Computer Simulation; D006801:Humans; D015233:Models, Statistical
keywords: Submodular functions; approximation; hypervolume indicator; matroid constraints; maximum cut; multiobjective optimization; runtime; theory