TY - GEN
T1 - Correlated Stochastic Knapsack with a Submodular Objective
AU - Yang, Sheng
AU - Khuller, Samir
AU - Choudhary, Sunav
AU - Mitra, Subrata
AU - Mahadik, Kanak
N1 - Funding Information:
Funding Samir Khuller and Sheng Yang were funded by an Amazon Research Award, and Adobe Research. Sheng Yang: Part of the work was done while at University of Maryland, College Park.
Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2022/9/1
Y1 - 2022/9/1
N2 - We study the correlated stochastic knapsack problem of a submodular target function, with optional additional constraints. We utilize the multilinear extension of submodular function, and bundle it with an adaptation of the relaxed linear constraints from Ma [Mathematics of Operations Research, Volume 43(3), 2018] on correlated stochastic knapsack problem. The relaxation is then solved by the stochastic continuous greedy algorithm, and rounded by a novel method to fit the contention resolution scheme (Feldman et al. [FOCS 2011]). We obtain a pseudo-polynomial time (1 - 1/ √ e)/2 ≃ 0.1967 approximation algorithm with or without those additional constraints, eliminating the need of a key assumption and improving on the (1-1/ 4 √e)/2 ≃ 0.1106 approximation by Fukunaga et al. [AAAI 2019].
AB - We study the correlated stochastic knapsack problem of a submodular target function, with optional additional constraints. We utilize the multilinear extension of submodular function, and bundle it with an adaptation of the relaxed linear constraints from Ma [Mathematics of Operations Research, Volume 43(3), 2018] on correlated stochastic knapsack problem. The relaxation is then solved by the stochastic continuous greedy algorithm, and rounded by a novel method to fit the contention resolution scheme (Feldman et al. [FOCS 2011]). We obtain a pseudo-polynomial time (1 - 1/ √ e)/2 ≃ 0.1967 approximation algorithm with or without those additional constraints, eliminating the need of a key assumption and improving on the (1-1/ 4 √e)/2 ≃ 0.1106 approximation by Fukunaga et al. [AAAI 2019].
KW - Stochastic Knapsack
KW - Stochastic Optimization
KW - Submodular Optimization
UR - http://www.scopus.com/inward/record.url?scp=85137549017&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85137549017&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2022.91
DO - 10.4230/LIPIcs.ESA.2022.91
M3 - Conference contribution
AN - SCOPUS:85137549017
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 30th Annual European Symposium on Algorithms, ESA 2022
A2 - Chechik, Shiri
A2 - Navarro, Gonzalo
A2 - Rotenberg, Eva
A2 - Herman, Grzegorz
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 30th Annual European Symposium on Algorithms, ESA 2022
Y2 - 5 September 2022 through 9 September 2022
ER -