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.
Original language | English (US) |
---|---|
Title of host publication | AAAI 2020 - 34th AAAI Conference on Artificial Intelligence |
Publisher | AAAI press |
Pages | 1460-1467 |
Number of pages | 8 |
ISBN (Electronic) | 9781577358350 |
State | Published - 2020 |
Event | 34th AAAI Conference on Artificial Intelligence, AAAI 2020 - New York, United States Duration: Feb 7 2020 → Feb 12 2020 |
Publication series
Name | AAAI 2020 - 34th AAAI Conference on Artificial Intelligence |
---|
Conference
Conference | 34th AAAI Conference on Artificial Intelligence, AAAI 2020 |
---|---|
Country/Territory | United States |
City | New York |
Period | 2/7/20 → 2/12/20 |
Bibliographical note
Funding Information:This work has been supported by the Australian Research Council through grant DP160102401, by the South Australian Government through the Research Consortium ”Un-
Funding Information:
This work has been supported by the Australian Research Council through grant DP160102401, by the South Australian Government through the Research Consortium”Unlocking Complex Resources through Lean Processing”, by the Paris Ile-de-France region, and by a public grant as part of the Investissement d'avenir project, reference ANR-11LABX-0056-LMH, LabEx LMH.
Publisher Copyright:
Copyright © 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.