# Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 23 Sep 2023.

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

- [Pareto Optimization for Subset Selection with Dynamic Cost Constraints](https://mlsanity.com/paper/1811.07806/) (2018)
- ["Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack](https://mlsanity.com/paper/1910.05646/) (2019)
- [Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms](https://mlsanity.com/paper/2006.11444/) (2020)
- [Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables](https://mlsanity.com/paper/2109.05799/) (2021)
- [Optimization of Chance-Constrained Submodular Functions](https://mlsanity.com/paper/1911.11451/) (2019)
- [Specific Single- and Multi-Objective Evolutionary Algorithms for the Chance-Constrained Knapsack Problem](https://mlsanity.com/paper/2004.03205/) (2020)
- [Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights](https://mlsanity.com/paper/2102.05778/) (2021)

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

- [Sampling-based Pareto Optimization for Chance-constrained Monotone Submodular Problems](https://mlsanity.com/paper/2404.11907/) (2024)

## Abstract (arXiv)

Chance constraints are frequently used to limit the probability of constraint violations in real-world optimization problems where the constraints involve stochastic components. We study chance-constrained submodular optimization problems, which capture a wide range of optimization problems with stochastic constraints. Previous studies considered submodular problems with stochastic knapsack constraints in the case where uncertainties are the same for each item that can be selected. However, uncertainty levels are usually variable with respect to the different stochastic components in real-world scenarios, and rigorous analysis for this setting is missing in the context of submodular optimization. This paper provides the first such analysis for this case, where the weights of items have the same expectation but different dispersion. We present greedy algorithms that can obtain a high-quality solution, i.e., a constant approximation ratio to the given optimal solution from the deterministic setting. In the experiments, we demonstrate that the algorithms perform effectively on several chance-constrained instances of the maximum coverage problem and the influence maximization problem.