# Liu et al. 2021 - Cardinality constrained submodular maximization for random streams

## One-paragraph Summary

Day la paper random-order streaming rat dang gia cho submodular maximization duoi cardinality. No day muc single-pass monotone streaming len muc toi uu `1 - 1 / e - eps` nhung van chi dung `O(k / eps)` memory thay vi phu thuoc mu vao `eps` nhu cong trinh truoc. Hon nua, paper mo rong y tuong sang non-monotone de dat `1 / e - eps` cung trong `O(k / eps)` memory. Tren phia lower bound, paper cung dong cot lai frontier bang hardness `1 - 1 / e + eps` cho monotone random-order single-pass streaming.

## Setup

- Objective: non-negative submodular `f : 2^E -> R_+`, monotone hoac non-monotone.
- Constraint: `|S| <= k`.
- Stream model: mot pass, random order.
- Complexity measure chinh: memory, tuc so phan tu lon nhat duoc buffer tai moi thoi diem.

## Main Results

1. Monotone case: algorithm single-pass dat `(1 - 1 / e - eps)` voi `O(k / eps)` memory.
2. Non-monotone case: algorithm single-pass dat `(1 / e - eps)` voi `O(k / eps)` memory.
3. Cac algorithm cung hoat dong gan nhu nguyen ven trong model `secretaries with shortlists`.
4. Hardness: bat ky `(1 - 1 / e + eps)`-approximation trong random-order strong-oracle model can `Omega(n)` memory cho general monotone submodular functions.

## Core Algorithmic Idea

- Chia stream ngau nhien thanh `alpha k` windows.
- Duy tri nhieu nghiem partial va mot pool `H` cac phan tu tung duoc dua vao mot nghiem ung vien.
- Pool `H` cho phep "tai dua" phan tu vao cac window sau trong phan tich, giu xac suat xuat hien doi xung can cho recurrence kieu greedy.
- Non-monotone variant chen them subsampling / filtering de tranh dua qua nhieu phan tu co the gay negative interaction vao nghiem.

## Proof / Analysis Strategy

- Random order cho phep xem moi optimum element la xuat hien trong cac window gan nhu dong deu.
- Phan tich recurrence cua best partial solution sau moi window mo phong greedy co `k` steps, dan den factor xap xi `1 - (1 - 1 / k)^k`.
- Hardness dung gadget coverage / hidden-good-elements: neu memory khong lon, stream algorithm khong the giu du thong tin de gom du tap good va vuot moc `1 - 1 / e`.

## Key Techniques

- random windows
- pooled reintroduction of previously seen good elements
- memory-optimal shortlist-compatible buffering
- greedy recurrence in random streams

## Delicate Points / Caveats

- Paper toi uu ve memory, nhung runtime khong toi uu; chinh tac gia ghi ro no cham hon `Sieve-Streaming`.
- Ket qua chi cho cardinality va random order, khong tu dong mo rong sang matroid / knapsack.
- Non-monotone ratio `1 / e` van cach xa frontier offline.

## Extraction To Concepts

- Chua can concept note rieng, nhung `syntheses/submodular.md` nen co nhanh random-order streaming.

## Extraction To Syntheses

- Them paper nay vao core papers cua `syntheses/submodular.md`.

## Weaknesses / Limits

- Khong practical nhat ve runtime.
- Proof relies manh vao random-order assumption.