# Sampling-based Pareto Optimization for Chance-constrained Monotone Submodular Problems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 18 Apr 2024.

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

- [Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms](https://mlsanity.com/paper/2006.11444/) (2020)
- [Optimization of Chance-Constrained Submodular Functions](https://mlsanity.com/paper/1911.11451/) (2019)
- [Evolutionary Algorithms for Limiting the Effect of Uncertainty for the Knapsack Problem with Stochastic Profits](https://mlsanity.com/paper/2204.05597/) (2022)
- [Solving Chance-Constrained Problems via a Smooth Sample-Based Nonlinear Approximation](https://mlsanity.com/paper/1905.07377/) (2019)
- [Specific Single- and Multi-Objective Evolutionary Algorithms for the Chance-Constrained Knapsack Problem](https://mlsanity.com/paper/2004.03205/) (2020)
- [Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives](https://mlsanity.com/paper/2002.06766/) (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)
- [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)
- [Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties](https://mlsanity.com/paper/2309.14359/) (2023)

## Abstract (arXiv)

Recently surrogate functions based on the tail inequalities were developed to evaluate the chance constraints in the context of evolutionary computation and several Pareto optimization algorithms using these surrogates were successfully applied in optimizing chance-constrained monotone submodular problems. However, the difference in performance between algorithms using the surrogates and those employing the direct sampling-based evaluation remains unclear. Within the paper, a sampling-based method is proposed to directly evaluate the chance constraint. Furthermore, to address the problems with more challenging settings, an enhanced GSEMO algorithm integrated with an adaptive sliding window, called ASW-GSEMO, is introduced. In the experiments, the ASW-GSEMO employing the sampling-based approach is tested on the chance-constrained version of the maximum coverage problem with different settings. Its results are compared with those from other algorithms using different surrogate functions. The experimental findings indicate that the ASW-GSEMO with the sampling-based evaluation approach outperforms other algorithms, highlighting that the performances of algorithms using different evaluation methods are comparable. Additionally, the behaviors of ASW-GSEMO are visualized to explain the distinctions between it and the algorithms utilizing the surrogate functions.