TY - JOUR
AU - Fukunaga, Takuro
AU - Konishi, Takuya
AU - Fujita, Sumio
AU - Kawarabayashi, Ken-ichi
PY - 2019/07/17
Y2 - 2024/07/20
TI - Stochastic Submodular Maximization with Performance-Dependent Item Costs
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 33
IS - 01
SE - AAAI Technical Track: Constraint Satisfaction and Optimization
DO - 10.1609/aaai.v33i01.33011485
UR - https://ojs.aaai.org/index.php/AAAI/article/view/3961
SP - 1485-1494
AB - <p>We formulate a new stochastic submodular maximization problem by introducing the performance-dependent costs of items. In this problem, we consider selecting items for the case where the performance of each item (i.e., how much an item contributes to the objective function) is decided randomly, and the cost of an item depends on its performance. The goal of the problem is to maximize the objective function subject to a budget constraint on the costs of the selected items. We present an adaptive algorithm for this problem with a theoretical guaran-√ tee that its expected objective value is at least (1−1<em>/</em> <sup>4</sup> <em>e</em>)<em>/</em>2 times the maximum value attained by any adaptive algorithms. We verify the performance of the algorithm through numerical experiments.</p>
ER -