Journal
EVOLUTIONARY COMPUTATION
Volume 23, Issue 4, Pages 543-558Publisher
MIT PRESS
DOI: 10.1162/EVCO_a_00159
Keywords
Submodular functions; matroid constraints; approximation; multiobjective optimization; hypervolume indicator; maximum cut; runtime; theory
Funding
- Australian Research Council (ARC) [DP140103400]
- European Union Seventh Framework Programme (FP7) [618091]
Ask authors/readers for more resources
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 theGSEMOachieves 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 + delta)- approximation in expected polynomial time for any constant delta > 0. Turning to nonmonotone symmetric submodular functions with k >= 1 matroid intersection constraints, we show that the GSEMO achieves a 1/((k + 2)(1 + epsilon))-approximation in expected time O(n(k+6) log(n)/epsilon).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available