# Dutting et al. 2024 - Consistent Submodular Maximization

## One-paragraph Summary

Day la paper mo ra mot truc danh gia khac voi query complexity hay approximation thuong thay: consistency, tuc so luong thay doi giua hai loi giai lien tiep khi stream co them mot phan tu moi. Trong setting monotone submodular maximization duoi cardinality constraint, paper dat cau hoi rat practical: co the giu loi giai on dinh qua thoi gian ma van con approximation co hang so hay khong? Cau tra loi la co, va paper dua ra hai thuoc toan co tradeoff ro rang: `Encompassing-Set` dat `1`-consistency va approximation `3.147 + O(1/k)`; `Chasing-Local-Opt` dat approximation tot hon `phi + 1 + 9 epsilon approx 2.619 + 9 epsilon` voi consistency `O~(1/epsilon)`. Dong thoi, paper chung minh mot lower bound thong tin hoc rat sach: voi bat ky hang so `C`, khong co deterministic `C`-consistent algorithm nao vuot qua `2 - epsilon`.

## Classification Rationale

Paper thuoc `submodular` vi no lam viec voi monotone set-submodular functions duoi cardinality. No giao thoa manh voi `streaming`, `dynamic insertion`, `stable optimization`, va `local-search`, nhung diem moi trung tam la consistency constraint tren loi giai dong, khong phai query complexity hay memory mot-pass theo nghia co dien.

## Setup

- Domain / model: monotone normalized submodular `f : 2^V -> R_+`.
- Stream model: insertion-only stream `e_1, ..., e_n`; tai thoi diem `t`, chi duoc chon tap `S_t subseteq V_t` voi `|S_t| <= k`.
- Performance notions: `alpha`-approximation nghia la `alpha * f(S_t) >= f(OPT_t)` moi `t`; `C`-consistency nghia la `|S_t \\ S_{t-1}| <= C` moi `t >= 2`.
- Assumptions: paper tap trung vao deterministic algorithms; lower bound cung nam trong setting deterministic.

## Main Results

1. Lower bound: voi moi constant `C` va moi `epsilon in (0,1)`, khong co deterministic `C`-consistent algorithm nao dat ratio tot hon `2 - epsilon`.
2. `Encompassing-Set`: thuat toan `1`-consistent, maintain benchmark set `B_t` va tra ve `S_t` la `k` phan tu vao benchmark gan nhat; dat approximation `3.147 + O(1/k)`.
3. `Chasing-Local-Opt`: thuat toan `O~(1/epsilon)`-consistent, update bang local improvements va them `N = ceil((1/epsilon) log_phi (12/epsilon))` buoc "chasing" sau moi insertion; dat approximation `(phi + 1 + 9 epsilon)`.
4. Paper bo sung thuc nghiem cho thay hai thuoc toan moi co objective value canh tranh voi `Swapping` / `Sieve-Streaming` trong khi giam tong so thay doi cua loi giai.

## Core Algorithmic Idea

Paper co hai y tuong trung tam, ung voi hai thuoc toan.

`Encompassing-Set` duy tri mot benchmark set `B_t`, co the infeasible theo cardinality. Phan tu moi `e_t` chi duoc them vao benchmark neu marginal contribution cua no du lon so voi benchmark hien tai: `f(e_t | B_{t-1}) >= (beta / k) f(B_{t-1})`, voi `beta = 1.14`. Loi giai thuc su `S_t` khong phai benchmark, ma la `k` phan tu duoc them vao benchmark gan nhat. Truc giac la benchmark giu lai "lich su cac cu huych lon", con `S_t` chi cat lay doan cuoi cua lich su do de dam bao consistency bang `1`.

`Chasing-Local-Opt` bo benchmark di va lam truc tiep tren loi giai hien tai. Neu phan tu moi hoac mot phan tu da den truoc do co marginal gain it nhat `phi / k` so voi gia tri hien tai cua loi giai, ta ep no vao bang `Min-Swap`: neu tap chua day thi them vao, con neu da day thi loai mot phan tu co marginal contribution khong vuot qua trung binh `f(S)/k`. Sau moi insertion, thuat toan khong dung lai ngay ma chay them toi da `N` lan de "chase" towards mot local optimum. Them swaps nay la cai gia phai tra de cai thien ratio tu `3.147` xuong `2.619 + o(1)`.

## Proof / Analysis Strategy

- Buoc 1: lower bound. Paper dung mot covering instance de chung minh neu loi giai bi rang buoc thay doi qua it sau moi insertion, thi doi thu co the dua vao mot phan tu moi buoc loi giai toi uu nhay sang mot vung moi ma loi giai on dinh cua ta khong theo kip; tu do khong the vuot qua `2 - epsilon`.
- Buoc 2: phan tich `Encompassing-Set`. Chung minh `f(OPT_t) <= (1 + beta) f(B_t)` vi moi phan tu optimum khong vao benchmark deu co marginal vao `B_t` nho hon `beta / k * f(B_t)`. Sau do chung minh benchmark khong the mat nhieu gia tri khi chi giu lai `k` phan tu cuoi: `f(B_t) >= (1 + beta/k)^k f(B_t \\ S_t)`. Ket hop hai inequality nay cho bound tren `f(S_t)`.
- Buoc 3: setup cho `Chasing-Local-Opt`. Dinh nghia notion local optimum: khong ton tai `x in V_t` sao cho `f(x|S_t) >= phi/k * f(S_t)`. Xem qua trinh tu thoi diem `tau` den `t` nhu mot chuoi swaps `s_1, ..., s_L` vao va `r_1, ..., r_L` ra, roi tao chuoi tap phu tro `A_l`.
- Buoc 4: neu `S_tau` la local optimum. Thi cac phan tu cu cua optimum deu co marginal nho doi voi `S_tau`, nen phan "old optimum" co the upper-bound bang `phi f(S_tau)`. Dong thoi tong gia tri mat di qua cac phan tu bi swap out co the bu duoc bang gain do cac swaps moi tao ra. Vi `phi^2 - phi - 1 = 0`, cac he so khop dep va cho factor `1 + phi + 4 epsilon`.
- Buoc 5: neu `S_tau` khong la local optimum. Khi do co rat nhieu swaps tu `tau` den `t`. Moi swap tao ra tang truong multiplicative it nhat `1 + (phi - 1)/k`, nen sau du nhieu swaps, gia tri loi giai hien tai ap dao gia tri cua bat ky optimum cu hon. Tu day co the bo qua phan `OPT_tau` va chi can charge cho phan tu den muon.
- Buoc 6: ghep hai truong hop va induction tren `t` de ra theorem `(phi + 1 + 9 epsilon)`.

## Key Techniques

- benchmark set voi nguong marginal tang theo gia tri benchmark
- cat `k` phan tu moi nhat de dat `1`-consistency
- min-swap bang phan tu co marginal contribution nho hon trung binh
- chasing local optimum bang mot so buoc phu sau moi insertion
- chia proof thanh hai regime: "co local optimum gan day" vs "da swap rat nhieu"

## Key Lemmas Or Structural Claims

- Khong vao benchmark thi marginal cua mot phan tu optimum vao benchmark hien tai bi chan boi `beta/k * f(B_t)`, tu do `f(OPT_t) <= (1 + beta)f(B_t)`.
- Gia tri benchmark giam theo cap so nhan khi bo dan cac phan tu cuoi ra, nen `B_t \\ S_t` chi chiem mot phan nho trong `f(B_t)`.
- Trong `Min-Swap`, luon ton tai mot phan tu co marginal contribution khong qua `f(S)/k`; day la averaging fact can thiet de thay phan tu bi swap out.
- Neu thuat toan thuc hien nhieu swaps, gia tri loi giai tang multiplicatively.
- He so vang `phi` duoc chon vi can bang dung term gain-loss trong inequality `phi^2 - phi - 1 = 0`.

## Delicate Points / Caveats

- "Consistency" o day la so phan tu thay doi giua hai loi giai lien tiep, khong phai so lan update noi bo hay query complexity.
- `Encompassing-Set` va `Chasing-Local-Opt` deu o insertion-only setting; ket qua khong tu dong mo rong sang fully dynamic co deletion.
- Approximation factors duoc viet theo convention `c`-approximation, nghia la `f(S_t) >= OPT_t / c`, khong phai ratio xap xi lon hon `1/2`.
- `Chasing-Local-Opt` can quet lai tap da den trong cac buoc phu; paper khong toi uu metric query/update-time theo cach streaming co dien.
- Lower bound la cho deterministic algorithms; randomized consistency line van mo.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: `C`-consistency, consistent submodular maximization, local optimum duoi nguong `phi/k`.
- Lemma co the tai su dung: trong tap kich thuoc `k`, ton tai phan tu co marginal `<= f(S)/k`.
- Technique lap lai: benchmark-set maintenance va proof hai-regime "local-optimum gan day / nhieu swaps".
- Quan he voi nhom khac: la mot nhanh song song voi streaming threshold line cua Badanidiyuru, nhung toi uu mot objective khac la stability chu khong phai chi memory/query.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` de mo mot nhanh moi: consistent / stable submodular maximization.
- Tao concept note rieng cho `consistent-submodular-maximization.md` la hop ly vi notion nay kha tai su dung va co lower bound rieng.
- Khong can cap nhat `k-submodular.md` hay `dr-submodular.md` truc tiep.

## Weaknesses / Limits

- Chi xu ly monotone objective duoi cardinality constraint.
- `Chasing-Local-Opt` cai thien ratio nhung consistency khong con la hang so `1`.
- Paper khong toi uu query complexity / running time nhu cac line "exactly n queries" hay streaming-memory papers.

## Research Ideas Triggered

- Kiem tra xem co randomized consistent algorithms nao co the pha moc `2` cua lower bound deterministic khong.
- Mo rong consistency notion sang matroid, knapsack, hay non-monotone settings.
- So sanh "stability as first-class objective" voi huong fully dynamic submodular maximization de xem co the chuyen machinery qua lai den muc nao.