# Ene and Nguyen 2022 - Streaming Algorithm for Monotone k-Submodular Maximization with Cardinality Constraints

## One-paragraph Summary

Day la paper streaming / online quan trong cho nhanh monotone `k`-submodular voi `per-coordinate cardinality constraints`, tuc moi label `i` co budget `B_i`. Khac voi greedy offline cua Ohsaka-Yoshida va khac ca threshold-greedy luu nhieu guesses, paper nay dua ra mot thuat toan primal-dual combinatorial chi giu mot nghiem feasible duy nhat, di mot pass qua stream, va van co guarantee hang so phu thuoc vao `B = min_i B_i`. Ty le dat duoc la `1 / (2(1 + B(2^(1/B) - 1)))`, bang `1/4` khi `B = 1` va tien dan den `1 / (2(1 + ln 2)) ~= 0.2953` khi budgets lon.

## Classification Rationale

Paper thuoc `k-submodular` vi no toi uu mot ham monotone `k`-submodular tren assignment domain `(k+1)^V`. Ve vai tro trong repo, no la cot moc cho nhanh `streaming / online` duoi `per-coordinate cardinality`, khac voi `total size` threshold-greedy offline cua Nie et al. 2023 va khac voi `knapsack streaming` cua Pham et al. 2022. Paper nay rat huu ich de dat vao synthesis vi no cho thay mot huong primal-dual online that su, khong chi la threshold guessing offline.

## Setup

- Domain / model: monotone `k`-submodular function `f : (k+1)^V -> R_+`, trong do nghiem la `k` tap roi nhau `S = (S_1, ..., S_k)`.
- Constraint: `|S_i| <= B_i` voi moi label `i`; dat `B = min_i B_i` va `r = sum_i B_i`.
- Access model: value oracle; khi mot phan tu `e` den, thuat toan query tat ca `k` marginals `Delta_(e,i) f(S)`.
- Streaming / online model: element den tung cai mot; trong free-disposal setting, thuat toan duoc phep thay mot phan tu cu bang mot phan tu moi de giu nghiem feasible.

## Main Results

1. Algorithm 1 cua paper la thuat toan single-pass cho monotone `k`-submodular under per-coordinate cardinality, dung `O(k|V|)` function evaluations, `O(sum_i B_i)` bo nho, va `O(|V|)` them thoi gian bo sung.
2. Approximation ratio la
   `1 / (2(1 + B(2^(1/B) - 1)))`.
   Ratio nay tang theo `B`, bang `1/4` khi `B = 1`, va hoi tu `1 / (2(1 + ln 2)) ~= 0.2953`.
3. Paper nhan manh thuat toan cung hop le cho online ad allocation voi free disposal, vi no luon duy tri mot nghiem feasible va khi phan tu moi den chi can quyet dinh them / bo tai cho.
4. Nhu mot side result, paper thich nghi khung nay cho monotone submodular maximization duoi partition matroid va dat ratio tot hon trong setting han che hon, tien dan den `0.3178`.

## Core Algorithmic Idea

Thuat toan giu cho moi label `i` mot nguong dong `phi_i` va mot deque `S_i`.

Khi phan tu `e` den:

- tinh `Delta_(e,j) f(S) - phi_j` cho moi label `j`
- chon label `i` co gia tri lon nhat
- neu gia tri tot nhat van khong am, chen `e` vao label `i`
- cap nhat nguong `phi_i` theo cong thuc affine-exponential
  `phi_i <- (1 + D / B_i) phi_i + (C / B_i) gamma_e`
  voi `gamma_e = Delta_(e,i) f(S) - phi_i`
- neu `S_i` vuot budget, loai phan tu den som nhat cua `S_i`

Truc giac cua paper la `phi_i` dong vai tro threshold cho marginal gains cua label `i`. Threshold nay tang dan theo thoi gian. Khi budget lon, threshold tang cham va mimics mot qua trinh lien tuc hon; khi budget nho, no tang nhanh hon de tranh giu qua nhieu phan tu gain thap. Viec bo phan tu cu nhat khi tran budget giup thuat toan luon feasible va phu hop voi streaming / online free disposal.

## Proof / Analysis Strategy

Paper dung mot khung primal-dual, day la diem khac biet lon nhat so voi threshold-greedy thong thuong.

- Buoc 1: viet mot primal LP cho bai toan `k`-submodular va mot dual LP tuong ung. Thuat toan online xay dong thoi mot nghiem primal integral `S` va cac bien dual `gamma_e`, `phi_i`.
- Buoc 2: chung minh cac bien dual tao boi thuat toan la feasible cho dual LP. `phi_i` dong vai tro gia tri "gia" cua budget label `i`, con `gamma_e` ghi nhan phan marginal vuot threshold cua phan tu duoc nhan.
- Buoc 3: viet ba dai luong
  - tong cac marginal gain da tich luy
  - gia tri nghiem cuoi `f(S)`
  - upper bound tren `f(S^*)`
  deu thanh linear combinations cua cac `gamma_e`.
- Buoc 4: so sanh he so cua tung `gamma_e` trong cac linear combinations do. Day la luc cong thuc update cua `phi_i` va viec luu deque / evict phan tu cu nhat tro nen quan trong.
- Buoc 5: chon tham so `C = 2D` va `D = B(2^(1/B) - 1)` de toi uu hoa ti le xau nhat giua cac he so, suy ra ratio cuoi cung.

Noi ngan gon, proof spine la: dual feasibility + weak duality upper-bounds `OPT`, con phan he so cua `gamma_e` cho lower bound tren gia tri thuat toan.

## Key Techniques

- primal-dual LP cho assignment-domain streaming
- per-label dynamic thresholds `phi_i`
- exponential-style threshold growth theo `B_i`
- single-solution maintenance, khong luu nhieu guesses
- deque eviction cua phan tu cu nhat de ho tro free disposal
- coefficient comparison tren cac bien dual `gamma_e`

## Key Lemmas Or Structural Claims

- Lemma 3.2 bieu dien tong marginal gains va gia tri nghiem cuoi thanh to hop tuyen tinh cua cac `gamma_e`, dua theo vi tri cua phan tu trong deque cua tung label.
- Lemma 3.3 chung minh cac `gamma_e`, `phi_i` do thuat toan sinh ra tao thanh mot nghiem dual feasible.
- Lemma 3.4 ket hop dual feasibility voi weak duality de upper bound `f(S^*)`.
- Lemma 3.5 lower-bound ratio giua cac he so lien quan den moi `gamma_e`; khi chon `C = 2D`, `D = B(2^(1/B) - 1)`, ratio toi thieu tro thanh `1 / (2(1 + B(2^(1/B) - 1)))`.

## Delicate Points / Caveats

- Paper xu ly `per-coordinate cardinality`, khong phai `total size`. Vi vay no khong thay the truc tiep cho note Nie et al. 2023; hai paper giai hai setting khac nhau.
- Ratio thap hon `1/3` offline greedy, doi lai la streaming / online, single pass, va khong can luu nhieu guesses.
- Thuat toan loai phan tu cu nhat, khong phai phan tu gain nho nhat. Paper co giai thich day la lua chon phu hop cho phan tich va cho free-disposal, du truc giac thuc nghiem co the goi y cac bien the khac.
- Metadata PDF ghi `Anonymous Submission`, nhung trang dau paper cho ro tac gia, venue la ICML 2022, va PMLR 162.

## Extraction To Concepts

- Bo sung vao `concepts/k-submodularity.md` mot nhanh ky thuat rieng: primal-dual streaming / online cho per-label cardinality, khac voi threshold-greedy offline va thresholding theo marginal-per-cost.
- Reusable ingredient: dynamic threshold `phi_i` tang theo cap so nhan va duoc canh chinh boi marginal cua phan tu vua duoc chon.
- Mot insight tai dung: khi budget lon, threshold growth mo phong tinh than "continuous" hon va ratio tang theo `B_min`.

## Extraction To Syntheses

- Chen paper nay vao `syntheses/k-submodular.md` nhu moc streaming / online cho per-coordinate cardinality.
- Trong synthesis can tach ro ba nhanh constraint:
  - per-coordinate cardinality streaming / online primal-dual
  - total / individual size offline threshold-greedy
  - knapsack streaming / thresholding
- Paper nay cung la cau noi tot de sau nay viet comparison note giua `single-solution primal-dual` va `multi-threshold guessing`.

## Weaknesses / Limits

- Ratio van thua offline greedy `1/3`, va thua threshold-greedy offline tren total-size `1/2 - epsilon`.
- Phan tich kha ky thuat vi di qua LP dual va so sanh he so, nen retrieval value nam o proof spine hon la pseudocode.
- Paper chi xu ly monotone case.

## Research Ideas Triggered

- So sanh primal-dual threshold tang dong cua paper nay voi threshold-greedy giam dan trong Nie et al. 2023.
- Kiem tra xem khung single-feasible-solution nay co the mo rong sang individual knapsack hay knapsack streaming hay khong.
- Viet mot note rieng cho "free disposal" trong k-submodular / ad allocation de noi paper nay voi partition-matroid submodular line.