# Non-Monotone Submodular Knapsack

## Related Groups

- submodular
- mixed

## Type

- problem-setting
- technique-cluster

## Statement

Non-monotone submodular maximization under a knapsack constraint tim tap `S` co `c(S) <= B` de toi da hoa mot ham submodular khong don dieu `f(S)`. Khac voi monotone case, them phan tu co the lam giam gia tri, nen greedy va thresholding phai kiem soat ca gain hien tai lan residual loss doi voi optimum.

## Intuition

Ba truc kho khan lap lai trong nhanh nay la:

- khong the chi giu "phan tu co marginal duong" nhu monotone case;
- knapsack lam cho local decisions ve density / threshold quan trong hon cardinality case;
- hieu nang thuc dung thuong do bang query complexity hoac adaptivity, khong chi approximation factor.

## Recurring Techniques

- split ground set theo cost
- dung hai candidate solutions roi nhau de absorb non-monotone interactions
- thresholding theo marginal-per-cost
- dung mot coarse constant-factor lower bound lam nen cho guessed-threshold routines
- doi tradeoff giua approximation, query complexity, va adaptivity

## Where It Is Used

- `2023-pham-et-al-linear-query-nonmonotone-knapsack`
- `2024-tran-et-al-parallel-nonmonotone-knapsack`