Correlated Stochastic Knapsack with a Submodular Objective
Preprint
Abstract
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/\sqrt{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/\sqrt[4]{e})/2 \simeq 0.1106$ approximation by Fukunaga et al. [AAAI 2019].
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Workloads in the Clouds2016
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution SchemesSIAM Journal on Computing, 2014
- A Unified Continuous Greedy Algorithm for Submodular Maximization2011
- Maximizing a Monotone Submodular Function Subject to a Matroid ConstraintSIAM Journal on Computing, 2011
- Stochastic Submodular Maximization2008
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)2007
- Batch mode active learning and its application to medical image classification2006
- Allocating Bandwidth for Bursty ConnectionsSIAM Journal on Computing, 2000
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- An analysis of approximations for maximizing submodular set functions—II1978