# Badanidiyuru et al. 2014 - Streaming Submodular Maximization

## One-paragraph Summary

Paper nay la moc quan trong khi submodular maximization buoc ra khoi che do offline. Dong gop trung tam la `Sieve-Streaming`: mot thuat toan single-pass cho monotone submodular maximization duoi rang buoc cardinality, dat xap xi `1/2 - epsilon` voi bo nho va update time rat nhe. Y tuong dep nhat cua paper la khong co gang biet chinh xac OPT; thay vao do, no chay song song nhieu bo loc nguong cho cac gia tri OPT du doan, va chung minh rang mot guess "gan dung" la du de cuu guarantee.

## Classification Rationale

Paper nam trong `submodular` vi no xu ly monotone set-submodular maximization. No giao thoa manh voi `streaming algorithms`, `large-scale summarization`, va la paper phai co neu muon theo doi dong greedy-threshold tu offline sang online / stream.

## Setup

- Domain / model: monotone submodular `f : 2^V -> R_+`.
- Oracle / access model: stream cac item di qua mot lan; co the truy van marginal gain cua item doi voi summary hien tai.
- Assumptions: rang buoc cardinality `k`; muc tieu la giu mot tap kich thuoc toi da `k` trong bo nho nho.

## Main Results

1. `Sieve-Streaming` dat approximation `1/2 - epsilon` cho monotone submodular maximization trong mot pass.
2. Bo nho va update time chi phu thuoc vao `k` va `epsilon`, khong phu thuoc truc tiep vao do dai stream.
3. Paper dua thuat toan tu muc ly thuyet xuong muc thuc dung cho cac bai toan summarization, active set selection, va clustering-style applications.

## Core Algorithmic Idea

Thay vi giu mot tap greedy duy nhat, paper giu nhieu candidate solutions, moi candidate ung voi mot guess `v` cho OPT. Voi moi candidate, item moi duoc them neu marginal gain cua no lon hon mot nguong phu thuoc vao `v`, gia tri da dat duoc hien tai, va so slot con lai. Truc giac la: neu doan dung OPT, thi threshold rule se ep rang moi item duoc chon dong gop du lon, con neu den cuoi tap van chua day `k` slot thi co nghia la phan residual cua OPT da qua nho de vuot khoi muc `1/2`.

## Proof / Analysis Strategy

- Buoc 1: tao luoi cac gia tri `v` de dam bao ton tai mot guess nam trong khoang hang so quanh OPT, su dung singleton max de dinh muc.
- Buoc 2: voi candidate dung guess, moi lan chap nhan item thi gia tri tang them it nhat mot threshold da duoc tinh de charge cho OPT.
- Buoc 3: tach hai truong hop: neu candidate du `k` item thi tong cac threshold cho ngay gia tri lon; neu candidate chua day `k` thi moi item cua OPT con lai deu co marginal nho hon threshold, nen residual so voi OPT da bi chan tu tren, dan den bound `1/2 - epsilon`.

## Key Techniques

- thresholded greedy trong streaming
- parallel guesses cho OPT
- singleton-based scaling de khoi tao threshold range
- case analysis "du k item" vs "chua du k item"

## Key Lemmas Or Structural Claims

- Luoi cac guess cho OPT luon co mot muc gan du de proof khong bi mat hang so qua nhieu.
- Neu mot item duoc chon boi candidate `v`, gain cua no dat mot lower bound theo residual budget con lai.
- Neu candidate dung guess tu choi moi item cua OPT con lai, thi tong marginal phan con lai cua OPT bi upper-bound boi so slot con lai nhan threshold.

## Delicate Points / Caveats

- Guarantee nay danh cho monotone objective va cardinality constraint; khong phai streaming framework tong quat cho moi rang buoc.
- `1/2 - epsilon` la cai gia de co mot pass, memory nho, va update time nhe; khong nen so truc tiep voi offline `1 - 1/e`.
- De doc proof, can phan biet ro `v` la guess cua OPT, khong phai gia tri hien tai cua summary.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: threshold streaming, guess-the-OPT grid, single-pass submodular maximization.
- Lemma co the tai su dung: "neu khong chon them duoc gi, residual OPT phai nho".
- Technique lap lai: duy tri nhieu threshold candidates song song de tranh phai biet OPT.
- Quan he voi nhom khac: la phien ban stream cua greedy lineage tu Nemhauser-Wolsey-Fisher.

## Extraction To Syntheses

- Cap nhat `syntheses/submodular.md` trong nhanh streaming / scalable optimization.
- `syntheses/k-submodular.md` co the nhac nhu mot dong cau hoi mo: co `Sieve-Streaming` analog cho k-submodular khong.
- `syntheses/dr-submodular.md` co the dung de so sanh voi threshold methods tren lattice / continuous domains.
- `syntheses/mixed.md` nen them neu lap synthesis ve "threshold as replacement for exact greedy".

## Weaknesses / Limits

- Chi xu ly cardinality; khong phai tong quat cho matroid hay rang buoc phuc tap trong mot pass.
- Guarantee `1/2 - epsilon` dung va dep, nhung van co khoang cach ro voi offline optimal approximation.

## Research Ideas Triggered

- Xem threshold-grid nay co the duoc phien dich sang DR-submodular cover tren stream hay khong.
- Theo doi mau proof "guess OPT + residual threshold" trong cac paper online / distributed submodular sau nay.