# Pham et al. 2022 - Maximizing k-Submodular Functions under Budget Constraint: Applications and Streaming Algorithms

## One-paragraph Summary

Day la paper journal ve `Budgeted k-Submodular Maximization (BkSM)`, trong do moi phan tu co the co mot cost chung hoac co cost khac nhau theo label, va tong cost cua nghiem bi chan boi mot budget `B`. Gia tri chinh cua paper la dua bai toan nay vao che do single-pass streaming va xu ly duoc ca monotone lan non-monotone. Paper xay hai tang ket qua: mot deterministic algorithm cho special case cost chung, dat `(1/4 - epsilon)` va `(1/5 - epsilon)`; va mot randomized algorithm cho general case cost phu thuoc label, dat constant-factor guarantees theo cac tham so `alpha`, `beta` do muc mat can bang chi phi.

## Classification Rationale

Paper thuoc `k-submodular` vi nghiem la `k` tap roi nhau tren domain `(k+1)^V`, nhung day cung la paper budgeted / knapsack co pham vi rong hon note DSAA 2022 da co. Khac voi DSAA 2022, bai nay khong chi lam viec voi cost chung `c(e)`, ma xu ly ca general case `c_i(e)`. Khac voi APJOR 2025 individual-knapsack, bai nay van la `single total budget`. Ve lineage, no la moc som cho dong streaming under budgeted constraints va co gia tri retrieval cao vi no dong thoi xu ly monotone + non-monotone.

## Setup

- Domain / model: `k`-submodular function `f : (k+1)^V -> R_+`.
- Constraint: tong cost cua nghiem `s = (S_1, ..., S_k)` thoa `sum_i sum_{e in S_i} c_i(e) <= B`.
- Hai setting: special case cost chung, va general case cost phu thuoc label.
- Access model: streaming value oracle; mot phan tu den mot lan, bo nho han che.
- Objective classes: ca monotone va non-monotone.

## Main Results

1. Algorithm 2 la deterministic single-pass streaming algorithm cho special case cost chung, voi query complexity `O(kn / epsilon * log n)` va space complexity `O(n / epsilon * log n)`.
2. Trong special case do, ratio la `(1/4 - epsilon)` cho monotone va `(1/5 - epsilon)` cho non-monotone.
3. Algorithm 4 la randomized single-pass streaming algorithm cho general case cost phu thuoc label, van co complexity cung bac `O(kn / epsilon * log n)` va `O(n / epsilon * log n)`.
4. O general case, paper dat ratio:
   - monotone: `min(alpha/2, (1-alpha)k / ((1+beta)k - beta)) - epsilon`
   - non-monotone: `min(alpha/2, (1-alpha)k / ((1+2beta)k - 2beta)) - epsilon`
   trong expectation, voi `beta` do ty le mat can bang chi phi giua cac label.

## Core Algorithmic Idea

Paper co hai lop thuat toan.

- Opt-known threshold template: voi mot lower bound `v <= OPT`, paper duyet stream, tim label tot nhat cho moi phan tu, va chi nhan neu marginal-per-cost vuot threshold. Cuoi cung giu nghiem tot nhat giua stream solution va best singleton; trong non-monotone case can giu them nghiem trung gian tot nhat.
- Guessed-opt wrapper: bo unknown-opt assumption bang luoi guesses hinh hoc cho `v`, dan den Algorithm 2.
- Generalized random choice: khi cost phu thuoc label, thresholding don gian tren label tot nhat khong con du. Paper dua vao mot random streaming template trong do xac suat chon label duoc thiet ke theo cost va marginal, roi wrap no bang outer guessing de thanh Algorithm 4.

## Proof / Analysis Strategy

- Special case: xay chuoi `s^j`, `o^j` va chung minh residual gap `v - f(o^t) <= f(s^t)` o monotone va `v - f(o^t) <= 2 f(s^t)` o non-monotone. Ket hop voi singleton fallback va guessed optimum de dat Theorem 2.
- General case: dinh nghia "bad element", phan tich one-step expected loss cua `o^j` boi expected gain cua `s^j`, voi he so phu thuoc `beta`. Sau do lap lai guessed-opt wrapper de dat Theorem 4.
- Xuyen suot paper, pairwise monotonicity la cong cu giu non-monotone case khong vo proof.

## Key Techniques

- single-pass threshold streaming
- guessed-opt wrapper voi luoi hinh hoc
- best singleton fallback
- residual-gap argument giua optimum da dong bo va nghiem stream
- random label selection theo marginal-per-cost
- dung pairwise monotonicity de giu non-monotone guarantee

## Key Lemmas Or Structural Claims

- Lemma 1: residual optimum sau khi dong bo bi chan boi `f(s^t)` o monotone va `2 f(s^t)` o non-monotone.
- Theorem 1: opt-known deterministic template dat moc `v/4` va `v/5` khi chon `alpha = 1/2`.
- Lemma 2: trong outer guessing loop, luon co mot guess `v` nam gan `OPT`.
- Lemma 3 / Theorem 3: trong general case, expected residual loss bi chan boi he so chua `beta`.
- Theorem 4: guessed-opt random streaming cho heterogeneous costs dat constant-factor guarantee in expectation.

## Delicate Points / Caveats

- Special case va general case la hai ket qua khac nhau that su, khong phai chi mot cai la phien ban don gian cua cai kia.
- DSAA 2022 trong repo hien tai co ratio dep hon cho mot so monotone common-cost settings, nen bai nay nen duoc doc nhu moc tong quat cho BkSM hon la diem cuoi state of the art.
- General-case ratios phu thuoc `beta`, nen guarantee nhay cam voi muc khong dong deu cua chi phi giua labels.
- Paper journal mo rong conference version bang proofs day du va experiment sach hon.

## Extraction To Concepts

- Bo sung vao `concepts/k-submodularity.md` mot nhanh rieng cho `budgeted k-submodularity` khi cost phu thuoc label.
- Reusable ingredient: guessed-opt streaming template cho `k`-submodular co the duoc nang cap tu deterministic sang randomized khi cost structure phuc tap hon.

## Extraction To Syntheses

- Cap nhat `syntheses/k-submodular.md` de danh dau budgeted line co hai nhanh: common-cost cleaner, va heterogeneous label-dependent costs can randomization.
- Paper nay nen dat truoc DSAA 2022 trong lineage budgeted streaming, vi no phat bieu bai toan tong quat hon.

## Weaknesses / Limits

- Complexity `O(kn / epsilon * log n)` khong dep bang cac bound query-linear hon cua mot so paper sau.
- General-case guarantee phu thuoc `beta`, nen kho so sanh nhanh neu khong co mot note concept tach rieng.

## Research Ideas Triggered

- Viet mot note so sanh `heterogeneous-cost budgeted k-submodular` voi `common-cost knapsack`.
- Kiem tra xem random distribution cua paper nay co lien he nao voi unconstrained randomized assignment line hay khong.