# Correlated Stochastic Knapsack with a Submodular Objective

arXiv: https://arxiv.org/abs/2207.01551 · HTML: https://mlsanity.com/paper/2207.01551/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2022.

## Built on by (most cited first, 1 of 1)

- [Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time](https://mlsanity.com/paper/2405.14183/) (2024)

## Abstract (arXiv)

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 simeq 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 simeq 0.1106 approximation by Fukunaga et al. [AAAI 2019].