# Linear-Query Submodular Maximization

## Related Groups

- submodular

## Type

- technique
- algorithmic-theme

## Statement

Huong nay toi uu hoa so lan query value oracle xuong muc tuyen tinh theo kich thuoc ground set `n`, trong khi van giu duoc approximation co hang so. Diem khac voi greedy / continuous-greedy co dien la query budget tro thanh tai nguyen chinh, nen thuat toan phai tranh recompute marginal nhieu lan.

## Intuition

Khi value oracle la nut that, mot query moi phan tu hoac hai query moi phan tu da la rat it. De lam duoc dieu nay, cac paper thuong phai "dong bang" thong tin tai luc phan tu den, hoac dung coarse lower bounds de quet threshold ma khong truy van lai qua nhieu.

## Equivalent Views

- query complexity as the primary optimization metric
- "fast but still provable" submodular maximization

## Standard Examples

- linear-query non-monotone knapsack voi `DLA` / `RLA`
- exactly-`n` / `2n` query algorithms cho matroid-constrained submodular maximization

## Related Results

- Pham et al. 2023 day non-monotone knapsack vao linear-query regime bang thresholding va coarse lower bounds
- Balkanski et al. 2024 dung infeasible-set querying va fixed arrival-time weights de dat exactly `n` queries cho monotone matroid MSM va `2n` queries cho general GSM
- o nhieu setting, linear-query algorithms phai hy sinh ratio so voi polynomial-query state of the art

## Where It Is Used

- `2023-pham-et-al-linear-query-nonmonotone-knapsack`
- `2024-balkanski-et-al-submodular-maximization-exactly-n-queries`