# Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences

arXiv: https://arxiv.org/abs/2104.09884 · HTML: https://mlsanity.com/paper/2104.09884/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 56 references that are in the map.
- First posted on arXiv 20 Apr 2021.

## Builds on (most cited first, 11 of 11)

- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- [Maximizing Submodular or Monotone Approximately Submodular Functions by Multi-objective Evolutionary Algorithms](https://mlsanity.com/paper/1711.07214/) (2017)
- [Pareto Optimization for Subset Selection with Dynamic Cost Constraints](https://mlsanity.com/paper/1811.07806/) (2018)
- [Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms](https://mlsanity.com/paper/2006.11444/) (2020)
- [Adaptive Sequence Submodularity](https://mlsanity.com/paper/1902.05981/) (2019)
- [String Submodular Functions with Curvature Constraints](https://mlsanity.com/paper/1303.3018/) (2013)
- [Maximizing Monotone Submodular Functions over the Integer Lattice](https://mlsanity.com/paper/1503.01218/) (2015)
- [Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms](https://mlsanity.com/paper/2006.12773/) (2020)
- [Submodularity on Hypergraphs: From Sets to Sequences](https://mlsanity.com/paper/1802.09110/) (2018)
- [Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints](https://mlsanity.com/paper/2012.08738/) (2020)
- [Multi-objective Evolutionary Algorithms are Still Good: Maximizing Monotone Approximately Submodular Minus Modular Functions](https://mlsanity.com/paper/1910.05492/) (2019)

## Built on by (most cited first, 1 of 1)

- [Fast Pareto Optimization Using Sliding Window Selection](https://mlsanity.com/paper/2305.07178/) (2023)

## Abstract (arXiv)

Evolutionary algorithms (EAs) are general-purpose optimization algorithms, inspired by natural evolution. Recent theoretical studies have shown that EAs can achieve good approximation guarantees for solving the problem classes of submodular optimization, which have a wide range of applications, such as maximum coverage, sparse regression, influence maximization, document summarization and sensor placement, just to name a few. Though they have provided some theoretical explanation for the general-purpose nature of EAs, the considered submodular objective functions are defined only over sets or multisets. To complement this line of research, this paper studies the problem class of maximizing monotone submodular functions over sequences, where the objective function depends on the order of items. We prove that for each kind of previously studied monotone submodular objective functions over sequences, i.e., prefix monotone submodular functions, weakly monotone and strongly submodular functions, and DAG monotone submodular functions, a simple multi-objective EA, i.e., GSEMO, can always reach or improve the best known approximation guarantee after running polynomial time in expectation. Note that these best-known approximation guarantees can be obtained only by different greedy-style algorithms before. Empirical studies on various applications, e.g., accomplishing tasks, maximizing information gain, search-and-tracking and recommender systems, show the excellent performance of the GSEMO.