TY - GEN
T1 - Stochastic submodular maximization with performance-dependent item costs
AU - Fukunaga, Takuro
AU - Konishi, Takuya
AU - Fujita, Sumio
AU - Kawarabayashi, Ken Ichi
N1 - Funding Information:
∗The first author is supported by JSPS KAKENHI Grant Number JP17K00040 and JST PRESTO Grant Number JPMJPR1759. The second and the fourth authors are supported by JST ERATO Grant Number JPMJER1201. Copyright ⃝c 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Publisher Copyright:
© 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2019
Y1 - 2019
N2 - 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 guarantee that its expected objective value is at least (1 - 1/ v4 e)/2 times the maximum value attained by any adaptive algorithms. We verify the performance of the algorithm through numerical experiments.
AB - 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 guarantee that its expected objective value is at least (1 - 1/ v4 e)/2 times the maximum value attained by any adaptive algorithms. We verify the performance of the algorithm through numerical experiments.
UR - http://www.scopus.com/inward/record.url?scp=85090808110&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090808110&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85090808110
T3 - 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019
SP - 1485
EP - 1494
BT - 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019
PB - AAAI Press
T2 - 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Annual Conference on Innovative Applications of Artificial Intelligence, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019
Y2 - 27 January 2019 through 1 February 2019
ER -