# Balkanski et al. 2024 - Submodular Maximization in Exactly n Queries

## One-paragraph Summary

Paper nay nam thang vao mot cau hoi rat cu the: co the dat constant-factor approximation cho submodular maximization duoi matroid constraint voi query complexity tuyen tinh theo `n` hay khong? Cau tra loi cua paper la co, va theo mot cach rat tiet kiem: `QuickSwap` dat `1/4` cho monotone MSM chi bang dung `n` queries, `QuickSwapNM` dat constant factor `1/(6 + 4 sqrt(2))` cho general GSM chi bang `2n` queries, va extension sang `p`-matchoid giu duoc `n` queries voi ratio `1/(4p)`. Gia tri cua paper khong nam o ratio dep nhat, ma o cho no day query complexity xuong muc sat can duoi tu nhien "mot query moi phan tu" va lam dieu do bang mot y tuong structural khac voi greedy quen thuoc: query vao mot tap infeasible superset, dong bang marginal weight tai thoi diem den, roi dung exchange arguments tren cac weight da dong bang nay de phan tich.

## Classification Rationale

Paper thuoc `submodular` vi no lam viec voi set-submodular functions duoi matroid / p-matchoid constraints, khong co assignment-domain hay lattice structure. No giao thoa manh voi `query-efficient algorithms`, `matroid maximization`, `non-monotone submodular maximization`, va la mot paper moc cho huong "linear-query offline" trong repo.

## Setup

- Domain / model: nonnegative submodular set function `f : 2^N -> R_+`; monotonicity chi duoc gia dinh trong bai toan MSM va MSPM.
- Oracle / access model: value oracle cho `f` va independence oracle cho matroid / p-matchoid; metric chinh la so lan query `f`.
- Constraints: matroid `M = (N, I)` cho MSM/GSM; `p`-matchoid cho MSPM.
- Assumptions: efficiency duoc do boi query complexity, khong phai tong running time hay so independence queries.

## Main Results

1. `QuickSwap` dat deterministic `1/4`-approximation cho monotone submodular maximization under a matroid constraint bang dung `n` queries, tuc mot query moi phan tu.
2. `QuickSwapNM` dat deterministic `1/(6 + 4 sqrt(2))`-approximation cho general non-monotone submodular maximization under a matroid constraint bang dung `2n` queries, la ket qua linear-query dau tien cho GSM trong setting nay.
3. `QuickSwapPM` mo rong y tuong sang monotone `p`-matchoid va giu query complexity `n`, dat ratio `1/(4p)`.
4. Paper dua ra tight examples cho phan monotone `1/4`, nen machinery monotone khong chi la "proof loose".
5. Ban `v2` tu nhan mot caveat quan trong: phan monotone `n`-query / `1/4` trung voi mot ket qua truoc do cua Dutting et al.; vi vay dong gop ky thuat moi manh nhat cua preprint nay nam o phan non-monotone va p-matchoid.

## Core Algorithmic Idea

Y tuong cot loi la duy tri mot cap tap `A' subseteq A`, trong do `A'` luon feasible con `A` co the infeasible va chua tat ca cac phan tu tung nam trong `A'`. Khi phan tu `e` den, thuat toan query mot lan gia tri `f(e | A)` tren superset infeasible `A`, dong bang no thanh weight `delta_e`, va khong bao gio recompute nua. Sau do, thay vi so marginal hien tai cua `e` voi tung ung vien swap, thuat toan chi so `delta_e` voi weight nho nhat trong `A'` ma neu bo no ra thi `e` co the duoc chen vao. Chinh viec "dong bang weight tai luc den" nay la meo de query complexity rot xuong `n`: toi luc can quyet dinh swap, thuat toan khong can query them.

Cho non-monotone case, mot ban copy duy nhat khong du vi `f(O union A)` co the nho hon `f(O)`. Cach xu ly la chay hai ban sao roi nhau `A/A'` va `B/B'`: moi phan tu duoc giao cho ban sao nao cho marginal vao infeasible set lon hon. Su tach roi nhau nay cho phep control phan residual cua `O` voi it nhat mot trong hai copy.

## Proof / Analysis Strategy

- Buoc 1: phan monotone MSM. Chung minh `f(A') >= beta/(1+beta) * f(A)` bang cach theo doi tong weight cua phan feasible va infeasible set. Truc giac la moi lan `A` tang gia tri, `A'` cung phai tang mot phan hang so cua muc tang do vi dieu kien swap.
- Buoc 2: van phan monotone, can upper-bound `f(O union A)`. Paper dung mot exchange-graph / gatekeeper argument: moi phan tu optimal bi tu choi co the map injectively toi mot phan tu trong `A'` chiu trach nhiem "chan cua", va weight cua gatekeeper du lon de charge cho phan tu do. Tu day suy ra `f(O union A) <= f(A) + (1 + beta) f(A')`.
- Buoc 3: ket hop hai bound tren va monotonicity `f(O) <= f(O union A)` de ra `f(O) <= ((1+beta)^2 / beta) f(A')`; toi uu tai `beta = 1`, cho ratio `1/4`.
- Buoc 4: phan non-monotone GSM. Chay hai copy disjoint `A/A'` va `B/B'`, moi phan tu di vao copy co marginal lon hon. Sau do su dung lemmata cua phan monotone tren tung copy rieng va mot inequality kieu `max{f(O union A)-f(A), f(O union B)-f(B)} <= (1+beta)(f(A')+f(B'))`.
- Buoc 5: ghep hai bound residual lai voi non-negativity va disjointness `A cap B = empty`, roi toi uu hoa theo `beta` de ra factor `1/(6 + 4 sqrt(2))`.
- Buoc 6: cho `p`-matchoid, thay vi tim mot phan tu swap duy nhat, paper xay `ExchangeCandidate` bang cach gom toi da mot phan tu tu moi constituent matroid. Diem dep la toan bo quyet dinh van dung cac `delta_x` da query truoc, nen khong dot ngot tang query complexity.

## Key Techniques

- query marginal vao infeasible superset thay vi chi query tap feasible
- dong bang arrival-time weights `delta_e` de tranh re-query
- exchange graph / injective gatekeeper mapping trong matroid analysis
- two-disjoint-copy reduction cho non-monotone objectives
- p-matchoid exchange candidate construction khong can function re-queries

## Key Lemmas Or Structural Claims

- `f(A') >= beta/(1+beta) * f(A)` cho phan monotone, va thuc ra lemma nay chi can submodularity, chua can monotonicity.
- Co ton tai mot injection tu moi tap feasible `S` vao `A'` sao cho phan tu anh xa co weight khong nho hon `delta_a/(1+beta)`; day la xuong song cua exchange proof.
- `f(O union A) <= f(A) + (1+beta)f(A')` la upper bound quyet dinh cho phan monotone.
- O non-monotone case, doi voi it nhat mot trong hai infeasible sets `A, B`, phan residual `f(O union A)-f(A)` hoac `f(O union B)-f(B)` co the duoc absorb boi `f(A') + f(B')`.
- Trong p-matchoid, moi exchange chi can loai ra mot tap ung vien kich thuoc toi da `p`, mot ung vien cho moi constituent matroid vi pham.

## Delicate Points / Caveats

- Can doc ky `A'` va `A`: `A'` moi la nghiem feasible tra ra; `A` la object phan tich, co the infeasible.
- Paper dem query value oracle, khong toi uu hoa so independence queries hay arithmetic operations. Vi vay "exactly `n` queries" khong dong nghia moi metric chi phi deu tuyen tinh.
- Ratio `1/4` cho monotone rat dep ve query complexity nhung van thap hon rat xa so voi `1 - 1/e`; day la tradeoff speed-versus-quality ro rang.
- Ban `v2` tu noi technical contribution cua phan monotone bi han che vi trung voi ket qua truoc do; do do khi dat paper nay vao synthesis, nen xem no la moc cho non-monotone linear-query matroid va viewpoint unifying hon la "phat minh" monotone `n`-query.
- Tight examples cua Section 2.4 chi ra machinery monotone nay khong phai chi loose analysis don thuan.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: linear-query submodular maximization, infeasible-set querying, arrival-time weights.
- Lemma co the tai su dung: gatekeeper injection tu optimum vao nghiem feasible duoc xay bang exchange graphs.
- Technique lap lai: chay nhieu copies disjoint de xu ly non-monotone objective ma khong tang query complexity hon cap hang.
- Quan he voi nhom khac: noi query-complexity line trong matroid setting voi linear-query non-monotone knapsack line cua Pham et al. 2023.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` trong nhanh fast / linear-query algorithms cho matroid constraints.
- Tao concept note rieng cho `linear-query-submodular-maximization.md` la hop ly vi y tuong nay da xuat hien o nhieu constraint classes trong repo.
- Khong can cap nhat `k-submodular.md` hay `dr-submodular.md` truc tiep.

## Weaknesses / Limits

- Approximation ratios con xa best known polynomial-query bounds.
- Phan monotone khong con hoan toan moi theo chinh ghi chu version 2 cua tac gia.
- Paper chu yeu toi uu query complexity; neu bai toan cua ta bi gioi han boi adaptivity, streaming memory, hay independence queries thi chua chac day la framework tot nhat.

## Research Ideas Triggered

- So sanh kieu "query infeasible superset" nay voi threshold streaming va hoi khi nao hai truong phai co the thong nhat.
- Xem co the dua ky thuat two-disjoint-copy sang non-monotone knapsack linear-query de cai thien factor `4 + epsilon` cua Pham et al. 2023 hay khong.
- Kiem tra xem feasible-set-only algorithms co the cung dat `n` queries cho matroid MSM hay khong; paper dat cau hoi nay rat ro.