# Tran et al. 2025 - k-Submodular Maximization Under Individual Knapsack Constraints: Applications and Streaming Algorithm

## One-paragraph Summary

Day la ban journal mo rong va lam dep rat ro cho conference paper SoICT 2023 ve `kSMIK`. Gia tri chinh cua paper la dua bai toan `k`-submodular duoi `individual knapsack constraints` vao che do streaming co guarantee ro rang hon, va quan trong hon la mo rong phan tich tu monotone sang ca non-monotone. Paper de xuat `StrOpt` va `Str`, trong do `Str` la deterministic two-pass streaming algorithm voi query complexity `O(Bk log(n) / epsilon)` va approximation factor duoc paper viet theo dang `2(k+1)/(1-epsilon)` cho monotone va `2k+3` cho non-monotone.

## Classification Rationale

Paper thuoc `k-submodular` va nam trong nhanh `individual-knapsack`. So voi DSAA 2022, no thay tong budget bang budget rieng theo label; so voi SoICT 2023, no la ban journal co pham vi rong hon, phan tich day hon, va bo sung non-monotone case. Day la canonical paper journal rieng, khong nen gop chung voi conference version.

## Setup

- Domain / model: `k`-submodular function tren assignment domain `(k+1)^V`.
- Constraint: moi label `i` co budget rieng `B_i`; paper gom chung thanh tham so `B` trong complexity bounds.
- Oracle / access model: streaming value-oracle model, bo nho han che.
- Objective classes: ca monotone va non-monotone deu duoc ban journal phan tich.

## Main Results

1. `StrOpt` giai quyet bai toan khi co mot lower bound / guess hop le cho optimum.
2. `Str` dung hai passes va mot luoi guesses hinh hoc de bo unknown-opt assumption, voi query complexity `O(Bk log(n) / epsilon)` va space complexity `O(B log(n) / epsilon)`.
3. Journal version mo rong guarantee sang non-monotone objective, trong khi conference version chu yeu dong khung monotone.
4. Thuc nghiem tren `k`-topic influence maximization va `k`-type sensor placement cho thay `Str` re query hon greedy baseline va thuong co quality canh tranh.

## Core Algorithmic Idea

Giong nhieu paper streaming khac trong repo, cot loi la "thresholding + guessed optimum". Diem moi o day la thresholding phai song chung voi nhieu budget labels.

`StrOpt` duyet stream mot lan. Voi moi phan tu, no tim label tot nhat va chi them vao neu hai dieu kien dong thoi dung: (i) label-budget van kha thi, va (ii) marginal gain vuot threshold dat tu guess `v` cua optimum. Nhu vay, moi nhan / label duoc dieu tiet boi cung mot khung threshold nhung rang buoc budget rieng.

`Str` wrap `StrOpt` trong mot outer procedure: tao mot day guesses cho optimum, chay `StrOpt` cho tung guess, va giu nghiem tot nhat. Vi paper muon giu tinh streaming, no co hai passes thay vi moi lan scan lai tuy y.

## Proof / Analysis Strategy

- Buoc 1: trong `StrOpt`, dong bo optimum `o` voi nghiem stream `s^j` va chung minh gia tri optimum bi mat khong vuot qua tong gain ma `s^j` da tich luy.
- Buoc 2: xet hai truong hop kinh dien: hoac khong con phan tu optimum nao vuot threshold, hoac co mot phan tu vuot threshold nhung bi budget chan. Hai case nay tra ve lower bound hang so.
- Buoc 3: doi voi non-monotone case, paper can them pairwise monotonicity / `k`-submodular structure de bound residual loss manh hon monotone argument don gian.
- Buoc 4: outer guessing loop trong `Str` chi can logarithmic so guesses de bao dam co mot guess nam gan optimum.

## Key Techniques

- threshold streaming duoi nhieu budget labels
- best singleton fallback
- guessed-opt wrapper xay tren `StrOpt`
- mo rong argument tu monotone sang non-monotone
- dung pairwise monotonicity / `k`-submodularity de control residual terms

## Key Lemmas Or Structural Claims

- Trong `StrOpt`, residual optimum sau khi dong bo voi nghiem stream bi chan boi gia tri nghiem stream.
- Neu mot phan tu optimum co gain lon nhung khong chen duoc vi budget, ket hop singleton va nghiem hien tai cho lower bound hang so.
- Co mot guess `v` trong outer loop nam du gan optimum de toan bo phan tich cua `StrOpt` van giu.
- Non-monotone case duoc bound bang mot he so yeu hon monotone, dan toi factor `2k + 3`.

## Delicate Points / Caveats

- Paper viet guarantee theo "approximation factor" kieu nghich dao; can doc can than de khong nham voi ratio lon hon 1.
- Complexity phu thuoc vao `B`; trong ung dung co budget lon, day co the la han che quan trong.
- Journal version nhac lai nhieu noi dung cua conference 2023, nhung pham vi va proof du rong de xem nhu mot canonical paper rieng.

## Extraction To Concepts

- Bo sung `individual knapsack` vao `concepts/k-submodularity.md`.
- Day la moc nen neu sau nay repo co them paper `k`-submodular multi-budget / streaming.

## Extraction To Syntheses

- Cap nhat `syntheses/k-submodular.md` voi nhanh individual-knapsack va streaming.
- Nhac ro lien he: SoICT 2023 la conference precursor, APJOR 2025 la journal extension.

## Weaknesses / Limits

- Complexity van phu thuoc vao `B`, khong dep bang cac paper total-budget query-linear theo `n`.
- Paper khong dat ratio dep nhu nhieu setting total-cardinality / matroid trong `k`-submodular.
- Mo rong non-monotone co factor kha yeu, chu yeu co gia tri "co guarantee dau tien / deterministic streaming".

## Research Ideas Triggered

- So sanh `individual-knapsack` voi `total-knapsack` de xem khi nao nhieu budget categories thuc su lam kho proof.
- Tim kha nang loai bo phu thuoc vao `B` hoac giam so passes ma van giu deterministic guarantees.