Publications
カンファレンス (国際) Stochastic Submodular Maximization with Performance-Dependent Item Costs
Takuro Fukunaga (RIKEN), Takuya Konishi (NII), Sumio Fujita, Ken-ichi Kawarabayashi (NII)
The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19)
2019.1.27
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 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 guarantee that its expected objective value is at least (1-1/root(e,4))/2 times the maximum value attained by any adaptive algorithms. We verify the performance of the algorithm through numerical experiments.