# Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 15 references that are in the map.
- First posted on arXiv 19 Jun 2024.

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

- [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)
- [Faster Guarantees of Evolutionary Algorithms for Maximization of Monotone Submodular Functions](https://mlsanity.com/paper/1908.01230/) (2019)
- [Fast Pareto Optimization Using Sliding Window Selection](https://mlsanity.com/paper/2305.07178/) (2023)

## Abstract (arXiv)

Constrained submodular optimization problems play a key role in the area of combinatorial optimization as they capture many NP-hard optimization problems. So far, Pareto optimization approaches using multi-objective formulations have been shown to be successful to tackle these problems while single-objective formulations lead to difficulties for algorithms such as the (1+1)-EA due to the presence of local optima. We introduce for the first time single-objective algorithms that are provably successful for different classes of constrained submodular maximization problems. Our algorithms are variants of the (1+λ)-EA and (1+1)-EA and increase the feasible region of the search space incrementally in order to deal with the considered submodular problems.