Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties
Files
(Published version)
Date
2023
Authors
Yan, X.
Do, A.V.
Shi, F.
Qin, X.
Neumann, F.
Editors
Fujita, H.
Perez-Meana, H.
Hernandez-Matamoros, A.
Perez-Meana, H.
Hernandez-Matamoros, A.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the 26th European Conference on Artificial Intelligence (ECAI 2023), as published in Frontiers in Artificial Intelligence and Applications, 2023 / Fujita, H., Perez-Meana, H., Hernandez-Matamoros, A. (ed./s), vol.372, pp.2826-2833
Statement of Responsibility
Xiankun Yan, Anh Viet Do, Feng Shi, Xiaoyu Qin and Frank Neumann
Conference Name
26th European Conference on Artificial Intelligence (ECAI) (30 Sep 2023 - 4 Oct 2023 : Kraków, Poland)
Abstract
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.
School/Discipline
Dissertation Note
Provenance
Description
This Conference includes the 12th Conference on Prestigious Applications of Intelligent Systems (PAIS 2023).
Access Status
Rights
© 2023 The Authors. This article is published online with Open Access by IOS Press and distributed under the terms of the Creative Commons Attribution Non-Commercial License 4.0 (CC BY-NC 4.0).