Beyond pointwise submodularity: Non-monotone adaptive submodular maximization subject to knapsack and k-system constraints.

Although the knapsack-constrained and k -system-constrained non-monotone adaptive submodular maximization have been well studied in the literature, it has only been settled given the additional assumption of pointwise submodularity. In this paper, we remove the common assumption on pointwise submodularity and propose the first approximation solutions for both knapsack and k -system constrained adaptive submodular maximization problems. Inspired by two recent studies on non-monotone adaptive submodular maximization, we develop a sampling-based randomized algorithm that achieves a 1 10 approximation ratio for the case of a knapsack constraint and that achieves a 1 2 k + 4 approximation ratio for the case of a k -system constraint. • We study the non-monotone adaptive submodular maximization problem. • We present a 1 10 approximation algorithm for knapsack constraints. • We present a 1 2 k + 4 approximation algorithm for k -system constraints. • Our results do not rely on pointwise submodularity. [ABSTRACT FROM AUTHOR]