Stochastic Submodular Maximization with Performance-Dependent Item Costs

Authors

  • Takuro Fukunaga PRESTO
  • Takuya Konishi National Institute of Informatics
  • Sumio Fujita Yahoo Japan Corporation
  • Ken-ichi Kawarabayashi National Institute of Informatics

DOI:

https://doi.org/10.1609/aaai.v33i01.33011485

Abstract

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/ 4e)/2 times the maximum value attained by any adaptive algorithms. We verify the performance of the algorithm through numerical experiments.

Downloads

Published

2019-07-17

How to Cite

Fukunaga, T., Konishi, T., Fujita, S., & Kawarabayashi, K.- ichi. (2019). Stochastic Submodular Maximization with Performance-Dependent Item Costs. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 1485-1494. https://doi.org/10.1609/aaai.v33i01.33011485

Issue

Section

AAAI Technical Track: Constraint Satisfaction and Optimization