Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
ISSN
1063-6560
E-ISSN
1530-9304
2014 Impact factor:
2.37

Evolutionary Computation

Winter 2015, Vol. 23, No. 4, Pages 543-558
(doi: 10.1162/EVCO_a_00159)
© 2015 Massachusetts Institute of Technology
Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms
Article PDF (290.5 KB)
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 ≥ 2 matroids, we show that the (1 +1) EA achieves a (1/δ)-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 .