Optimization of Chance-Constrained Submodular Functions

Authors

  • Benjamin Doerr cole Polytechnique
  • Carola Doerr Sorbonne University
  • Aneta Neumann The University of Adelaide
  • Frank Neumann The University of Adelaide
  • Andrew Sutton University of Minnesota

DOI:

https://doi.org/10.1609/aaai.v34i02.5504

Abstract

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.

Downloads

Published

2020-04-03

How to Cite

Doerr, B., Doerr, C., Neumann, A., Neumann, F., & Sutton, A. (2020). Optimization of Chance-Constrained Submodular Functions. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1460-1467. https://doi.org/10.1609/aaai.v34i02.5504

Issue

Section

AAAI Technical Track: Constraint Satisfaction and Optimization