# Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2020.

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

- [3-Objective Pareto Optimization for Problems with Chance Constraints](https://mlsanity.com/paper/2304.08774/) (2023)
- [Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem](https://mlsanity.com/paper/2404.06014/) (2024)
- [Fast Pareto Optimization Using Sliding Window Selection](https://mlsanity.com/paper/2305.07178/) (2023)
- [Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences](https://mlsanity.com/paper/2104.09884/) (2021)
- [Benchmarking Algorithms for Submodular Optimization Problems Using IOHProfiler](https://mlsanity.com/paper/2302.01464/) (2023)
- [Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties](https://mlsanity.com/paper/2309.14359/) (2023)
- [Bi-objective chance-constrained evolutionary optimization for large-scale open-pit mine scheduling under geological uncertainty](https://mlsanity.com/paper/2511.08275/) (2025)
- [On the use of evolutionary optimization for the dynamic chance constrained open-pit mine scheduling problem](https://mlsanity.com/paper/2604.13385/) (2026)
- [Sampling-based Pareto Optimization for Chance-constrained Monotone Submodular Problems](https://mlsanity.com/paper/2404.11907/) (2024)
- [Sliding Window 3-Objective Pareto Optimization for Problems with Chance Constraints](https://mlsanity.com/paper/2406.04899/) (2024)
- [Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization](https://mlsanity.com/paper/2406.13414/) (2024)
- [Adaptive Operator Selection in Bilevel Large Neighborhood Search for Electric Autonomous Dial-a-Ride Problem under Uncertainty](https://mlsanity.com/paper/2610.04219/) (2026)

## Abstract (arXiv)

Many real-world optimization problems can be stated in terms of submodular functions. Furthermore, these real-world problems often involve uncertainties which may lead to the violation of given constraints. A lot of evolutionary multi-objective algorithms following the Pareto optimization approach have recently been analyzed and applied to submodular problems with different types of constraints. We present a first runtime analysis of evolutionary multi-objective algorithms based on Pareto optimization for chance-constrained submodular functions. Here the constraint involves stochastic components and the constraint can only be violated with a small probability of alpha. We investigate the classical GSEMO algorithm for two different bi-objective formulations using tail bounds to determine the feasibility of solutions. We show that the algorithm GSEMO obtains the same worst case performance guarantees for monotone submodular functions as recently analyzed greedy algorithms for the case of uniform IID weights and uniformly distributed weights with the same dispersion when using the appropriate bi-objective formulation. As part of our investigations, we also point out situations where the use of tail bounds in the first bi-objective formulation can prevent GSEMO from obtaining good solutions in the case of uniformly distributed weights with the same dispersion if the objective function is submodular but non-monotone due to a single element impacting monotonicity. Furthermore, we investigate the behavior of the evolutionary multi-objective algorithms GSEMO, NSGA-II and SPEA2 on different submodular chance-constrained network problems. Our experimental results show that the use of evolutionary multi-objective algorithms leads to significant performance improvements compared to state-of-the-art greedy algorithms for submodular optimization.