TY - JOUR AU - Fukunaga, Takuro AU - Konishi, Takuya AU - Fujita, Sumio AU - Kawarabayashi, Ken-ichi PY - 2019/07/17 Y2 - 2024/03/28 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 -