2022/07/04 by Sheng Yang, Samir Khuller, Yang, Sheng +7
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.2207.01551
Accepted to ESA 2022. (fix typo in previous version)
arxiv created 2022/08/03 · arxiv updated 2022/08/04
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].