Correlated Stochastic Knapsack with a Submodular Objective
share
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/√(e))/2 ≃ 0.1106 approximation by Fukunaga et al. [AAAI 2019].
READ FULL TEXT