TY - GEN
T1 - Partial-Adaptive Submodular Maximization
AU - Tang, Shaojie
AU - Yuan, Jing
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - The goal of a typical adaptive sequential decision making problem is to design an interactive policy that selects a group of items sequentially, based on some partial observations, to maximize the expected utility. It has been shown that the utility functions of many real-world applications, including pooled-based active learning and adaptive influence maximization, satisfy the property of adaptive submodularity. However, most studies on adaptive submodular maximization focus on fully adaptive settings, which can take a long time to complete. In this paper, we propose a partial-adaptive submodular maximization approach where multiple selections can be made in a batch and observed together, reducing the waiting time for observations. We develop effective and efficient solutions for both cardinality and knapsack constraints and analyzes the batch query complexity. We are the first to explore partial-adaptive policies for non-monotone adaptive submodular maximization problems.
AB - The goal of a typical adaptive sequential decision making problem is to design an interactive policy that selects a group of items sequentially, based on some partial observations, to maximize the expected utility. It has been shown that the utility functions of many real-world applications, including pooled-based active learning and adaptive influence maximization, satisfy the property of adaptive submodularity. However, most studies on adaptive submodular maximization focus on fully adaptive settings, which can take a long time to complete. In this paper, we propose a partial-adaptive submodular maximization approach where multiple selections can be made in a batch and observed together, reducing the waiting time for observations. We develop effective and efficient solutions for both cardinality and knapsack constraints and analyzes the batch query complexity. We are the first to explore partial-adaptive policies for non-monotone adaptive submodular maximization problems.
UR - https://www.scopus.com/pages/publications/85164005845
U2 - 10.1007/978-3-031-34347-6_32
DO - 10.1007/978-3-031-34347-6_32
M3 - Conference contribution
AN - SCOPUS:85164005845
SN - 9783031343469
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 380
EP - 391
BT - Combinatorial Algorithms - 34th International Workshop, IWOCA 2023, Proceedings
A2 - Hsieh, Sun-Yuan
A2 - Hung, Ling-Ju
A2 - Lee, Chia-Wei
PB - Springer Science and Business Media Deutschland GmbH
T2 - 34th International Workshop on Combinatorial Algorithms, IWOCA 2023
Y2 - 7 June 2023 through 10 June 2023
ER -