Optimization of Chance-Constrained Submodular Functions - Sorbonne Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Optimization of Chance-Constrained Submodular Functions

Carola Doerr
Aneta Neumann
  • Fonction : Auteur
Frank Neumann
  • Fonction : Auteur
Andrew M Sutton
  • Fonction : Auteur

Résumé

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.
Fichier principal
Vignette du fichier
1911.11451.pdf (280.28 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02871943 , version 1 (17-06-2020)

Identifiants

  • HAL Id : hal-02871943 , version 1

Citer

Benjamin Doerr, Carola Doerr, Aneta Neumann, Frank Neumann, Andrew M Sutton. Optimization of Chance-Constrained Submodular Functions. AAAI-20 Thirty-Fourth AAAI Conference on Artificial Intelligence, Feb 2020, New York, United States. ⟨hal-02871943⟩
126 Consultations
107 Téléchargements

Partager

Gmail Facebook X LinkedIn More