TY - GEN
T1 - Constrained Stochastic Submodular Maximization with State-Dependent Costs
AU - Tang, Shaojie
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - In this paper, we study the constrained stochastic submodular maximization problem with state-dependent costs. The input of our problem is a set of items whose states (i.e., the marginal contribution and the cost of an item) are drawn from a known probability distribution. The only way to know the realized state of an item is to select that item. We consider two constraints, i.e., inner and outer constraints. Recall that each item has a state-dependent cost, and the inner constraint states that the total realized cost of all selected items must not exceed a give budget. Thus, inner constraint is state-dependent. The outer constraint, on the other hand, is state-independent. It can be represented as a downward-closed family of sets of selected items regardless of their states. Our objective is to maximize the objective function subject to both inner and outer constraints. Under the assumption that larger cost indicates larger “utility”, we present a constant approximate solution to this problem.
AB - In this paper, we study the constrained stochastic submodular maximization problem with state-dependent costs. The input of our problem is a set of items whose states (i.e., the marginal contribution and the cost of an item) are drawn from a known probability distribution. The only way to know the realized state of an item is to select that item. We consider two constraints, i.e., inner and outer constraints. Recall that each item has a state-dependent cost, and the inner constraint states that the total realized cost of all selected items must not exceed a give budget. Thus, inner constraint is state-dependent. The outer constraint, on the other hand, is state-independent. It can be represented as a downward-closed family of sets of selected items regardless of their states. Our objective is to maximize the objective function subject to both inner and outer constraints. Under the assumption that larger cost indicates larger “utility”, we present a constant approximate solution to this problem.
UR - https://www.scopus.com/pages/publications/85138823781
U2 - 10.1007/978-3-031-16081-3_11
DO - 10.1007/978-3-031-16081-3_11
M3 - Conference contribution
AN - SCOPUS:85138823781
SN - 9783031160806
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 121
EP - 132
BT - Algorithmic Aspects in Information and Management - 16th International Conference, AAIM 2022, Proceedings
A2 - Ni, Qiufen
A2 - Wu, Weili
PB - Springer Science and Business Media Deutschland GmbH
T2 - 16th International Conference on Algorithmic Aspects in Information and Management, AAIM 2022
Y2 - 13 August 2022 through 14 August 2022
ER -