Correlated Stochastic Knapsack with a Submodular Objective

30th Annual European Symposium on Algorithms (ESA)

Publication date: September 1, 2022

Sheng Yang, Samir Khuller, Sunav Choudhary, Subrata Mitra, Kanak Mahadik

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 approximation algorithm with or without those additional constraints, eliminating the need of a key assumption and improving on the $(1 - 1/\sqrt[4]{e})/2 \simeq 0.1106$ approximation by Fukunaga et al. [AAAI 2019].

Learn More

Research Area:  Adobe Research iconAI & Machine Learning