Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties

Simple item page
dc.contributor.authorYan, X.
dc.contributor.authorDo, A.V.
dc.contributor.authorShi, F.
dc.contributor.authorQin, X.
dc.contributor.authorNeumann, F.
dc.contributor.conference26th European Conference on Artificial Intelligence (ECAI) (30 Sep 2023 - 4 Oct 2023 : Kraków, Poland)
dc.contributor.editorFujita, H.
dc.contributor.editorPerez-Meana, H.
dc.contributor.editorHernandez-Matamoros, A.
dc.date.issued2023
dc.descriptionThis Conference includes the 12th Conference on Prestigious Applications of Intelligent Systems (PAIS 2023).
dc.description.abstractChance 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.
dc.description.statementofresponsibilityXiankun Yan, Anh Viet Do, Feng Shi, Xiaoyu Qin and Frank Neumann
dc.identifier.citationProceedings 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
dc.identifier.doi10.3233/faia230594
dc.identifier.isbn9781643684369
dc.identifier.issn0922-6389
dc.identifier.issn1879-8314
dc.identifier.orcidYan, X. [0000-0002-2309-8034]
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttps://hdl.handle.net/2440/148484
dc.language.isoen
dc.publisherIOS Press
dc.relation.granthttp://purl.org/au-research/grants/arc/FT200100536
dc.relation.ispartofseriesFrontiers in Artificial Intelligence and Applications; 372
dc.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).
dc.source.urihttps://ebooks.iospress.nl/volume/ecai-2023-26th-european-conference-on-artificial-intelligence-including-12th-conference-on-prestigious-applications-of-intelligent-systems-pais-2023?_gl=1*1typzbu*_up*MQ..*_ga*MTc1ODIzMjcyMi4xNzY1MzI1NDkw*_ga_6N3Q0141SM*czE3NjUzMjU0ODkkbzEkZzAkdDE3NjUzMjU0ODkkajYwJGwwJGgw
dc.titleOptimizing Chance-Constrained Submodular Problems with Variable Uncertainties
dc.typeConference paper
pubs.publication-statusPublished

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
hdl_148484.pdf
Size:
868.96 KB
Format:
Adobe Portable Document Format
Description:
Published version
Download

Collections

Research Outputs