Correlated Stochastic Knapsack with a Submodular Objective

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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].

Original languageEnglish (US)
Title of host publication30th Annual European Symposium on Algorithms, ESA 2022
EditorsShiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772471
StatePublished - Sep 1 2022
Event30th Annual European Symposium on Algorithms, ESA 2022 - Berlin/Potsdam, Germany
Duration: Sep 5 2022Sep 9 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference30th Annual European Symposium on Algorithms, ESA 2022


  • Stochastic Knapsack
  • Stochastic Optimization
  • Submodular Optimization

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Correlated Stochastic Knapsack with a Submodular Objective'. Together they form a unique fingerprint.

Cite this