# Nie et al. 2023 - Size-Constrained k-Submodular Maximization in Near-Linear Time

## One-paragraph Summary

Day la paper threshold-greedy quan trong cho nhanh `k`-submodular co rang buoc kich thuoc. Paper xu ly dong thoi hai setting: `total size` (mot budget chung cho tong so item duoc gan nhan) va `individual size` (moi label co budget rieng). Dong gop cot loi la giu duoc cac deterministic ratios tot nhat da biet, len den `(1/2 - epsilon)` va `(1/3 - epsilon)`, trong khi day so lan value-oracle calls xuong `O(nk / epsilon * log(B / epsilon))`. Diem nay xoa phu thuoc tuyen tinh vao budget `B` cua greedy co dien, va trong case individual-size con cat them mot he so `k` so voi stochastic greedy truoc do.

## Classification Rationale

Paper thuoc `k-submodular` vi nghiem van la assignment tren `(k+1)^V`, nhung no rat quan trong cho nhanh constrained maximization. So voi Ohsaka-Yoshida 2015, paper nay khong co tham vong cai thien ratio, ma cai thien oracle complexity bang thresholding theo phong cach Badanidiyuru-Vondrak cua submodular `k = 1`. Ve retrieval, day la paper can dat canh cac paper knapsack / streaming vi no cho thay total-size va individual-size da co near-linear deterministic algorithms trong offline setting.

## Setup

- Domain / model: monotone `k`-submodular function `f : (k+1)^V -> R_+`, hay tuong duong la ham tren tap cac item-type pairs khong trung item.
- Oracle / access model: value oracle; marginal gain viet duoi dang `f((e,i) | S)`.
- Constraints:
  - Problem 1: total size `|U(S)| <= B`.
  - Problem 2: individual size `|U_i(S)| <= B_i` voi moi label `i`.
- Assumptions: `f` khong am, monotone, va duoc chuan hoa `f(emptyset) = 0`.

## Main Results

1. Algorithm 1 (`Threshold Greedy-TS`) dat `(1/2 - epsilon)` cho total size constraint voi `O(nk / epsilon * log(B / epsilon))` function evaluations.
2. Algorithm 2 (`Threshold Greedy-IS`) dat `(1/3 - epsilon)` cho individual size constraints cung voi `O(nk / epsilon * log(B / epsilon))` evaluations.
3. Ve mat so sanh literature, paper giu nguyen deterministic ratios cua Ohsaka-Yoshida 2015 nhung bo duoc yeu to `B` trong complexity. O case IS, no cung tranh duoc yeu to `k` phu troi cua stochastic greedy.
4. Paper con co thuc nghiem tren sensor placement `k` types va influence maximization `k` topics, cho thay threshold greedy giu objective value gan greedy / stochastic greedy trong khi tiet kiem queries ro ret.

## Core Algorithmic Idea

Hai thuat toan deu dung mot song nguong giam dan, bat dau tu
`d = max_(e,i) f({(e,i)})`,
tuc best singleton value.

Voi moi threshold `tau`, thuat toan quet qua cac item-type pair con feasible. Neu marginal gain `f((e,i) | S)` dat nguong, pair do duoc chen ngay vao nghiem. Sau mot vong quet, nguong giam thanh `(1 - epsilon) tau`, roi lap lai cho den khi threshold xuong du thap.

Co hai diem quan trong.

- Thresholding cho phep them nhieu item trong mot pass, nen khong can moi lan chi chen mot item nhu greedy co dien. Day la nguon goc giam complexity tuyen tinh theo `B` xuong chi con log-phu thuoc vao `B`.
- Trong case individual-size, thay vi stochastic sampling de giam chi phi, paper van xet tat ca pair con feasible o moi threshold. Nho vay no tranh duoc bai toan phai sample "dung" cho tung label, do do tranh duoc he so `k` them vao complexity.

## Proof / Analysis Strategy

### Total Size

- Dat `S^circ` la nghiem cuoi, `S_j` la prefix sau `j` lan them.
- Canh hang mot nghiem toi uu `OPT` bang cach can index cac pair trong `OPT` sao cho neu item da xuat hien trong `S^circ` thi dung cung index.
- Xay chuoi `O_0 = OPT, O_1, ..., O_B = S^circ`, trong do `O_(j+1)` thay pair thu `j+1` cua `OPT` bang pair thu `j+1` do threshold greedy da chon.
- Dung Lemma 1 cua Tang et al. de chan `f(O_j) - f(O_(j+1))` boi tong cac marginal. Vi pair tu `OPT` dang xet da tung la feasible khi thuat toan chon pair thu `j+1`, marginal cua no bi threshold chan tren trong khoang he so `1 / (1 - epsilon)`.
- Cong don qua tat ca `j` cho ra bound so sanh giua `f(OPT)` va `f(S^circ)`. Khi nghiem chua day du budget, paper dung threshold cuoi cung de chan tong gain cua phan con thieu. Ket qua cuoi la `(1/2 - epsilon)`.

### Individual Size

Proof chi tiet nam trong supplementary, va day la phan retrievable nhat cua bai.

- Van xay chuoi trung gian giua `OPT` va nghiem output, nhung khong the doi mot pair mot cach don gian, vi thay type o vi tri `j+1` co the lam vuot budget cua mot label.
- Vi vay paper chen them mot buoc trung gian `O_(j+1/2)`: tim mot pair khac trong `O_j` co cung label voi pair thu `j+1` ma greedy da chon, roi doi type cua hai pair truoc; sau do moi thay item o vi tri `j+1`.
- Chuoi `O_j -> O_(j+1/2) -> O_(j+1)` giu feasibility cho moi label budget, va cho phep lap lai exchange-style argument.
- Tong hop qua toan bo chuoi cho ra ratio `(1/3 - epsilon)`.

## Key Techniques

- decreasing threshold schedule tu best singleton
- add-many-per-pass de cat linear dependence on budget
- lazy-evaluable threshold scans
- exchange-style proof voi nghiem toi uu da can index
- type-swapping construction cho individual budgets
- dung monotonicity + orthant-submodularity de bound residual gain cua optimum

## Key Lemmas Or Structural Claims

- Lemma 1 (trich tu Tang et al. 2022): voi `S subseteq S'`, phan gain chenh lech `f(S') - f(S)` duoc chan boi tong cac marginal tren `S' \ S`; day la xuong song cua proof.
- Trong total-size, moi pair cua `OPT` canh vao pair greedy cung chi so da tung la feasible; neu no khong duoc chon, marginal cua no phai thap hon threshold hien tai hoac threshold vong truoc.
- Trong individual-size, can doi type truoc roi moi doi item de giu moi budget `B_i`; do do supplementary xay cac nghiem trung gian `O_(j+1/2)`.
- Khi output chua dung het budget, tong gain co the bo sung them bi chan boi threshold ket thuc nhan voi phan budget con lai; day la ly do threshold floor duoc dat theo `epsilon d / (2B)` hay `epsilon d / (3B)` tuy theo bai toan.

## Delicate Points / Caveats

- Paper yeu cau monotonicity; no khong xu ly non-monotone size-constrained case.
- Ratios `(1/2 - epsilon)` va `(1/3 - epsilon)` khong cai thien best-known approximation factors, ma cai thien value-oracle complexity.
- Proof individual-size khong nam tron trong main paper; muon truy hoi proof spine thi phai doc supplementary `nie23a-supp.pdf`.
- Thuat toan la offline threshold greedy, khong phai streaming. No nen duoc so sanh voi greedy / stochastic greedy offline hon la voi DSAA 2022 streaming.

## Extraction To Concepts

- Bo sung vao `concepts/k-submodularity.md` rang total-size va individual-size deu co threshold-greedy near-linear line, khong chi co greedy `O(nkB)` hay streaming.
- Reusable ingredient: under individual size constraints, giu feasibility can doi type giua hai positions truoc khi doi item; day la motif proof co the lap lai trong cac bai multi-budget assignment.
- Kien truc threshold giam dan tu best singleton la cau noi ro rang tu set-submodular `k = 1` sang `k`-submodular.

## Extraction To Syntheses

- Cap nhat `syntheses/k-submodular.md` de tach rieng nhanh size constraints thanh total-size va individual-size, va ghi ro rang paper UAI 2023 la moc near-linear deterministic.
- Nen dat paper nay canh Ohsaka-Yoshida 2015 trong synthesis nhu mot "runtime improvement without ratio improvement".
- Co the dung paper nay lam diem noi giua offline size constraints va streaming knapsack papers trong repo.

## Weaknesses / Limits

- Khong xu ly knapsack hay matroid; paper tap trung vao size constraints.
- Dung threshold scans tren toan bo `V x [k]`, nen du near-linear theo oracle complexity nhung van la offline full-pass style.
- Ve proof, phan subtle nhat nam o individual-size va bi day sang supplementary; neu mat file supplement thi se mat mot phan gia tri retrieval cua paper.

## Research Ideas Triggered

- Tao comparison note rieng cho `size constraints` trong `k`-submodular: Ohsaka-Yoshida greedy vs stochastic greedy vs Nie et al. threshold greedy.
- Kiem tra xem type-swapping proof cho IS co the chuyen hoa sang individual knapsack hay matroid partition duoi assignment-domain hay khong.