# Optimization of Chance-Constrained Submodular Functions

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2019.

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

- [Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)](https://mlsanity.com/paper/2112.08581/) (2021)
- [3-Objective Pareto Optimization for Problems with Chance Constraints](https://mlsanity.com/paper/2304.08774/) (2023)
- [Advances in Set Function Learning: A Survey of Techniques and Applications](https://mlsanity.com/paper/2501.14991/) (2025)
- [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)
- [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)

## Abstract (arXiv)

Submodular optimization plays a key role in many real-world problems. In many real-world scenarios, it is also necessary to handle uncertainty, and potentially disruptive events that violate constraints in stochastic settings need to be avoided. In this paper, we investigate submodular optimization problems with chance constraints. We provide a first analysis on the approximation behavior of popular greedy algorithms for submodular problems with chance constraints. Our results show that these algorithms are highly effective when using surrogate functions that estimate constraint violations based on Chernoff bounds. Furthermore, we investigate the behavior of the algorithms on popular social network problems and show that high quality solutions can still be obtained even if there are strong restrictions imposed by the chance constraint.