# Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to Knapsack and k-System Constraints

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 18 references that are in the map.
- First posted on arXiv 10 Apr 2021.

## Builds on (most cited first, 6 of 6)

- [Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint](https://mlsanity.com/paper/2007.05014/) (2020)
- [Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time](https://mlsanity.com/paper/2008.05004/) (2020)
- [Optimal Sampling Gaps for Adaptive Submodular Maximization](https://mlsanity.com/paper/2104.01750/) (2021)
- [No Time to Observe: Adaptive Influence Maximization with Partial Feedback](https://mlsanity.com/paper/1609.00427/) (2016)
- [Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio](https://mlsanity.com/paper/1904.10748/) (2019)
- [Price of Dependence: Stochastic Submodular Maximization with Dependent Items](https://mlsanity.com/paper/1905.09719/) (2019)

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

- [Group Equality in Adaptive Submodular Maximization](https://mlsanity.com/paper/2207.03364/) (2022)
- [Robust Adaptive Submodular Maximization](https://mlsanity.com/paper/2107.11333/) (2021)
- [Partial-Monotone Adaptive Submodular Maximization](https://mlsanity.com/paper/2207.12840/) (2022)
- [Streaming Adaptive Submodular Maximization](https://mlsanity.com/paper/2208.08021/) (2022)
- [Partial-Adaptive Submodular Maximization](https://mlsanity.com/paper/2111.00986/) (2021)
- [Data Summarization beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization](https://mlsanity.com/paper/2309.05183/) (2023)
- [Worst-Case Adaptive Submodular Cover](https://mlsanity.com/paper/2210.13694/) (2022)
- [The Power of Second Chance: Personalized Submodular Maximization with Two Candidates](https://mlsanity.com/paper/2409.03545/) (2024)

## Abstract (arXiv)

In this paper, we study the non-monotone adaptive submodular maximization problem subject to a knapsack and a k-system constraints. The input of our problem is a set of items, where each item has a particular state drawn from a known prior distribution. However, the state of an item is initially unknown, one must select an item in order to reveal the state of that item. There is a utility function which is defined over items and states. Our objective is to sequentially select a group of items to maximize the expected utility. Although the cardinality-constrained non-monotone adaptive submodular maximization has been well studied in the literature, whether there exists a constant approximation solution for the knapsack-constrained or k-system constrained adaptive submodular maximization problem remains an open problem. It fact, 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 constant approximation solutions for both cases. Inspired by two recent studies on non-monotone adaptive submodular maximization, we develop a sampling-based randomized algorithm that achieves a frac110 approximation for the case of a knapsack constraint and that achieves a frac12k+4 approximation ratio for the case of a k-system constraint.