# Pham et al. 2022 - Fast Streaming Algorithms for k-Submodular Maximization under a Knapsack Constraint

## One-paragraph Summary

Day la paper theo huong constrained streaming cho `k`-submodular maximization, cu the la bai toan monotone `k`-submodular maximization duoi mot rang buoc knapsack. Dong gop chinh cua paper khong nam o ratio tot nhat tuyet doi, ma o viec day query complexity xuong muc tuyen tinh theo `n k` trong khi van giu duoc constant approximation. Paper dua ra hai thuat toan xac dinh: `FSA`, single-pass, dat `1/10` voi `O(nk)` queries; va `IFSA`, multi-pass, dat `1/4 - epsilon` voi `O(nk / epsilon)` queries bang cach dung nghiem coarse cua `FSA` de khoa mot day nguong threshold hop ly.

## Classification Rationale

Paper thuoc `k-submodular` vi doi tuong la ham tren domain `(k+1)^V`, moi phan tu co the duoc gan vao mot trong `k` nhan roi nhau. No giao thoa manh voi `streaming`, `knapsack`, `thresholding`, va `query-efficient approximation`. So voi Ward-Zivny 2014 la paper nen tang unconstrained, paper nay dich chuyen nhanh sang setting co chi phi va bo nho / so lan query la tai nguyen can toi uu.

## Setup

- Domain / model: ham `f : (k+1)^V -> R_+`, monotone `k`-submodular, voi nghiem la `k`-set gom `k` tap roi nhau.
- Oracle / access model: value-oracle / marginal-oracle; voi moi phan tu `e`, thuat toan query tat ca `k` vi tri de tim nhan co gain tot nhat.
- Constraint: moi phan tu `e` co cost `c(e) > 0`, tong cost cua nghiem phai khong vuot budget `B`.
- Assumptions: paper lam viec voi truong hop monotone; phan tich khong phu thuoc vao vi du ung dung cu the.

## Main Results

1. `FSA` la deterministic single-pass streaming algorithm dau tien trong repo cho bai toan nay dat constant ratio voi chi `O(nk)` queries; guarantee cu the la `1/10`.
2. `IFSA` cai thien ratio len `1/4 - epsilon` bang cach quet them `O(1 / epsilon)` pass va van giu query complexity `O(nk / epsilon)`.
3. Ve thuc nghiem, paper cho thay `FSA` va `IFSA` doi luc mat chat luong so voi cac doi thu query-nang, nhung giam query va thoi gian rat manh tren hai bai toan ung dung: `k`-topic influence maximization va `k`-type sensor placement.

## Core Algorithmic Idea

Paper co hai tang y tuong.

`FSA` tach ground set thanh hai mien theo cost:

- phan tu `heavy` voi `c(e) > B / 2`, khi do bat ky nghiem feasible nao tren mien nay chi co toi da mot phan tu, nen chi can luu singleton tot nhat;
- phan tu `light` voi `c(e) <= B / 2`, khi do thuat toan duyet stream va chap nhan `(e, i_e)` neu marginal gain tai nhan tot nhat dat nguong
  `Delta_(e, i_e) f(s) >= c(e) f(s) / B`.

Sau khi duyet xong, `FSA` khong tra ve toan bo day da nhan ma cat lay mot suffix co tong cost gan `B` nhat nhung van khong vuot `B`, roi so sanh suffix do voi heavy singleton tot nhat.

`IFSA` dung `FSA` nhu mot coarse estimator. Neu `Gamma = f(s_max)` la gia tri nghiem cua `FSA`, thi tu ratio `1/10` suy ra
`Gamma <= OPT <= 10 Gamma`.
Tu day, `IFSA` quet mot luoi nguong hinh hoc
`theta = 5 (1 - epsilon)^t Gamma / B`
va o moi pass chi nhan nhung phan tu co marginal-per-cost du lon. Y tuong la trong mot pass "dung nguong", threshold se nam gan muc `OPT / (2B)`, du de suy ra ratio `1/4 - epsilon`.

## Proof / Analysis Strategy

Khung phan tich cua paper rat ro neu tach theo `FSA` va `IFSA`.

- Buoc 1: doi voi `FSA`, tach OPT thanh phan `heavy` va `light`. Phan `heavy` quy ve best singleton; phan `light` duoc phan tich qua nghiem stream tao boi nguong marginal theo cost.
- Buoc 2: chung minh nghiem light tam thoi `s^t` khong qua xa optimum light bang hai huong: gia tri OPT bi "mat" khi chen nghiem stream vao thi khong vuot qua gia tri nghiem stream, va phan residual cua OPT gom cac phan tu truot nguong cung khong the dong gop qua nhieu do moi phan tu deu co marginal-per-cost duoi nguong.
- Buoc 3: do `s^t` co the vuot budget, paper cat mot suffix feasible `s'` va chung minh suffix nay van giu duoc it nhat `1/3` gia tri cua `s^t`; ket hop voi bound tren optimum light cho ra `f(s') >= f(OPT_light) / 9`. Cong them best heavy singleton suy ra `1/10`.
- Buoc 4: doi voi `IFSA`, su dung `FSA` de dong khung OPT trong mot day threshold. O nguong phu hop, xet hai truong hop: co mot phan tu OPT dang co marginal lon nhung khong chen duoc vi budget sap day, hoac khong co phan tu nao nhu vay. Truong hop dau dung trung binh giua nghiem hien tai va best singleton; truong hop sau bound residual OPT boi `B theta`. Ca hai cung tra ve xap xi gan `OPT / 4`.

## Key Techniques

- cost partition `> B/2` vs `<= B/2`
- cost-normalized thresholding theo marginal-per-cost
- lay suffix feasible thay vi prefix feasible
- geometric threshold guessing tu coarse lower bound
- reuse mot constant-factor streaming routine de nang ratio o multi-pass phase

## Key Lemmas Or Structural Claims

- `f(OPT_light) - f(OPT_light^j) <= f(s^j)`: gia tri optimum light bi mat trong qua trinh "dong bo" voi nghiem stream khong vuot qua gain ma stream da tich luy.
- `f(s') >= f(s^t) / 3`: suffix feasible cat tu day stream van giu duoc hang so gia tri, do moi phan tu light deu co cost toi da `B/2`.
- `f(OPT_light^t) <= 2 f(s^t)`: phan residual cua optimum light sau khi bo cac phan tu truot nguong chi con dong gop toi da cung bac voi nghiem stream.
- Tu ba menh de tren suy ra `f(s') >= f(OPT_light) / 9`, roi cong voi best heavy singleton de dat `1/10`.
- O `IFSA`, voi threshold tot, hoac mot phan tu OPT co gain lon bi budget chan lai, hoac moi phan tu OPT con lai deu co marginal duoi nguong. Hai case nay lan luot tra ve lower bound xap xi `B theta / 2` va `OPT - (f(s_theta) + B theta)`, dan den `1/4 - epsilon`.

## Delicate Points / Caveats

- Paper yeu cau `monotone` `k`-submodular; khung proof khong mo rong truc tiep sang non-monotone.
- Ratio `1/10` cua `FSA` nho, nen y nghia thuc te cua no chu yeu la lower-bound re de khoa luoi threshold cho `IFSA`.
- Buoc lay suffix feasible la chi tiet de bi bo qua khi doc nhanh; day la cau noi giup nghiem stream vuot budget tro thanh nghiem knapsack hop le ma van con gia tri hang so.
- `IFSA` khong phai single-pass: cai thien ratio den tu viec quet lai stream nhieu lan tren luoi nguong hinh hoc.
- Phan trinh bay tieng Anh trong source kha tho va co mot vai ky hieu / chi so de doc nham, nhung spine cua chung minh van ro rang.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/`: `k`-submodular duoi knapsack constraint, marginal-per-cost thresholding trong assignment domain.
- Lemma co the tai su dung: heavy-vs-light partition cho knapsack khi phan `heavy` co toi da mot phan tu; residual-optimum bounded by failed threshold test.
- Technique lap lai: dung mot coarse constant-factor streaming algorithm de bracket `OPT`, roi chay decreasing-threshold multi-pass.
- Quan he voi nhom khac: co DNA rat gan voi threshold streaming cho submodular knapsack, nhung can them machinery cua assignment labels va `k`-submodularity.

## Extraction To Syntheses

- Cap nhat `syntheses/k-submodular.md` de danh dau buoc chuyen tu unconstrained maximization sang knapsack-constrained streaming.
- Khong can tao concept file moi tach rieng trong lan nay; bo sung vao `concepts/k-submodularity.md` la du.
- Chua can cap nhat truc tiep `syntheses/submodular.md` hay `syntheses/dr-submodular.md`.

## Weaknesses / Limits

- Ratios van yeu hon so voi greedy query-nang va mot so ket qua sau nay; paper danh doi kha manh lay query complexity.
- `IFSA` dat cung muc `1/4 - epsilon` voi mot streaming paper truoc do, diem moi o day la tiet kiem he so `log n` trong query complexity hon la cai thien approximation ratio.
- Bao cao thuc nghiem cho thay chat luong co the thap hon doi thu tren mot so bo du lieu, nen paper nay hop hon khi tai nguyen query / runtime la nut that that su.

## Research Ideas Triggered

- Tao mot comparison note rieng cho dong `k`-submodular under knapsack`: greedy query-nang vs single-pass thresholding vs multi-pass thresholding.
- Kiem tra xem heavy/light + suffix-truncation co mo rong duoc sang matroid-intersection hay budgeted multi-knapsack khong.
- So sanh truc tiep spine proof cua paper nay voi threshold streaming trong set-submodular de tach phan nao la "generic knapsack streaming" va phan nao thuc su can `k`-submodularity.