TY - GEN
T1 - Stochastic Submodular Probing with State-Dependent Costs
AU - Tang, Shaojie
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - In this paper, we study a new stochastic submodular maximization problem with state-dependent costs and rejections. The input of our problem is a budget constraint B, and 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 probe that item. We allow rejections, i.e., after probing an item and knowing its actual state, we must decide immediately and irrevocably whether to add that item to our solution or not. Our objective is to sequentially probe/select a best group of items subject to a budget constraint on the total cost of the selected items. We present a constant approximate solution to this problem. We show that our solution can be extended to an online setting.
AB - In this paper, we study a new stochastic submodular maximization problem with state-dependent costs and rejections. The input of our problem is a budget constraint B, and 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 probe that item. We allow rejections, i.e., after probing an item and knowing its actual state, we must decide immediately and irrevocably whether to add that item to our solution or not. Our objective is to sequentially probe/select a best group of items subject to a budget constraint on the total cost of the selected items. We present a constant approximate solution to this problem. We show that our solution can be extended to an online setting.
KW - Knapsack constraints
KW - State-dependent costs
KW - Stochastic submodular maximization
UR - https://www.scopus.com/pages/publications/85122003941
U2 - 10.1007/978-3-030-93176-6_15
DO - 10.1007/978-3-030-93176-6_15
M3 - Conference contribution
AN - SCOPUS:85122003941
SN - 9783030931759
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 170
EP - 178
BT - Algorithmic Aspects in Information and Management - 15th International Conference, AAIM 2021, Proceedings
A2 - Wu, Weili
A2 - Du, Hongwei
PB - Springer Science and Business Media Deutschland GmbH
T2 - 15th International Conference on Algorithmic Aspects in Information and Management, AAIM 2021
Y2 - 20 December 2021 through 22 December 2021
ER -