---
title: "Faster Guarantees of Evolutionary Algorithms for Maximization of Monotone Submodular Functions"
authors:
  - "Victoria G. Crawford"
doi: "10.24963/ijcai.2021/229"
url: "https://ijcai.org/proceedings/2021/229"
pdf: "https://ijcai.org/proceedings/2021/0229.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "1661-1667"
track: "Main Track"
keywords:
  - "Heuristic Search and Game Playing: Combinatorial Search and Optimisation"
---

# Faster Guarantees of Evolutionary Algorithms for Maximization of Monotone Submodular Functions

Victoria G. Crawford

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 1661-1667. DOI: [10.24963/ijcai.2021/229](https://doi.org/10.24963/ijcai.2021/229)

## Abstract

In this paper, the monotone submodular maximization problem (SM) is studied. SM is to find a subset of size kappa from a universe of size n that maximizes a monotone submodular objective function f . We show using a novel analysis that the Pareto optimization algorithm achieves a worst-case ratio of (1 − epsilon)(1 − 1/e) in expectation for every cardinality constraint kappa < P , where P ≤ n + 1 is an input, in O(nP ln(1/epsilon)) queries of f . In addition, a novel evolutionary algorithm called the biased Pareto optimization algorithm, is proposed that achieves a worst-case ratio of (1 − epsilon)(1 − 1/e − epsilon) in expectation for every cardinality constraint kappa < P in O(n ln(P ) ln(1/epsilon)) queries of f . Further, the biased Pareto optimization algorithm can be modified in order to achieve a a worst-case ratio of (1 − epsilon)(1 − 1/e − epsilon) in expectation for cardinality constraint kappa in O(n ln(1/epsilon)) queries of f . An empirical evaluation corroborates our theoretical analysis of the algorithms, as the algorithms exceed the stochastic greedy solution value at roughly when one would expect based upon our analysis.