# Tran et al. 2023 - Maximizing a k-Submodular Maximization Function under an Individual Knapsack Constraint

## One-paragraph Summary

Day la conference paper ngan nhung co gia tri mo duong: no chuyen bai toan `k`-submodular tu total knapsack sang `individual knapsack`, tuc moi label / source co budget rieng. Paper dua ra mot streaming framework gom `SAO` (biet truoc `OPT`) va `SA` (khong biet `OPT`) cho bai toan monotone `kSMIK`, voi approximation factor duoc paper viet theo dang `2(k+1)/(1-epsilon)` va query complexity `O(nk log(B) / epsilon)`. Ve mat thu thap tri thuc, day la ban conference precursor cua journal APJOR 2025, va rat quan trong de thay cach threshold streaming phai sua khi budget khong con duoc gom chung.

## Classification Rationale

Paper thuoc `k-submodular` vi no lam viec tren domain `(k+1)^V`. Khac voi paper DSAA 2022 duoi `total knapsack`, paper nay dua them cau truc `individual knapsack`, nen moi quyet dinh nhan phai dong thoi ton trong budget cua tung label. No la paper giao giua `k-submodular`, `streaming`, va `multiple budgets`.

## Setup

- Domain / model: monotone `k`-submodular function tren `k` tap roi nhau.
- Oracle / access model: value oracle, query tat ca `k` nhan de chon vi tri cho tung phan tu.
- Constraint: voi moi label `i`, tong cost cua cac phan tu gan vao `S_i` phai nho hon budget `B_i`.
- Assumptions: conference version chi phan tich ro truong hop monotone.

## Main Results

1. Paper gioi thieu `kSMIK`, mot bien the individual-budget cua `k`-submodular maximization ma paper khang dinh la chua duoc nghien cuu truc tiep truoc do.
2. `SAO` phan tich bai toan khi biet mot gia tri xap xi cua optimum, tu do chung minh lower-bound constant-factor cho template threshold streaming.
3. `SA` dung geometric guessing de bo assumption biet `OPT`, giu query complexity `O(nk log(B) / epsilon)` va tra ve streaming approximation dau tien cho setting nay.

## Core Algorithmic Idea

Y tuong giong DNA cua paper DSAA 2022 nhung kho hon vi budget duoc tach theo label. Thuat toan duyet stream va, voi moi phan tu, tim nhan tot nhat. Neu dua phan tu vao nhan do khong lam vuot budget cua nhan ay va marginal gain vuot mot nguong threshold, thi chap nhan.

`SAO` gia dinh da co mot uoc luong `v` cua `OPT`, nen nguong threshold duoc dat truc tiep theo `v`. `SA` sau do chay them mot outer loop de doan `v` qua mot luoi hinh hoc, roi lay nghiem tot nhat trong so cac lan chay. Ca hai deu luu them best singleton de tranh bo sot truong hop optimum bi thong tri boi mot phan tu lon.

## Proof / Analysis Strategy

- Buoc 1: phan tich `SAO` khi `v` nam trong day `(1 - epsilon) OPT <= v <= OPT`.
- Buoc 2: chung minh gia tri optimum bi mat sau moi lan dong bo voi nghiem stream khong vuot qua gia tri nghiem da tich luy; day la bien the `k`-submodular cua residual-gap argument.
- Buoc 3: xet hai truong hop: hoac khong con phan tu OPT nao vuot threshold, hoac co mot phan tu vuot threshold nhung bi budget label chan. Moi truong hop deu tra ve mot lower bound constant-factor.
- Buoc 4: outer loop cua `SA` chi can thu mot tap guesses hinh hoc cho `OPT`, tu do nang `SAO` thanh thuat toan tong quat.

## Key Techniques

- threshold streaming voi budget rieng cho tung label
- best singleton fallback
- opt-known template roi guessed-opt wrapper
- su dung ky thuat residual-gap quen thuoc trong `k`-submodular streaming

## Key Lemmas Or Structural Claims

- Neu moi phan tu OPT con lai deu duoi threshold, tong residual gain bi chan boi threshold nhan voi tong budget.
- Neu ton tai mot phan tu OPT co gain lon nhung khong chen duoc vi budget, ket hop singleton va nghiem hien tai cho lower bound hang so.
- Chi can thu mot day guesses hinh hoc cho `OPT` de loai bo assumption biet optimum.

## Delicate Points / Caveats

- Tieu de paper co ve bi lap tu "Maximization"; day co kha nang la typo ngay trong ban conference.
- Conference version ngan, nen proof va notation kha nen; journal APJOR 2025 mo rong va sach hon rat nhieu.
- Paper chu yeu trinh bay monotone case; journal version sau nay mo rong them non-monotone.

## Extraction To Concepts

- Dinh nghia / notation nen dua vao `concepts/k-submodularity.md`: individual knapsack constraints cho assignment-domain.
- Technique lap lai: opt-known threshold template + geometric guessing cho multi-budget k-submodular streaming.
- Quan he voi nhom khac: la cau noi tu total-knapsack `k`-submodular sang multi-budget setting.

## Extraction To Syntheses

- Cap nhat `syntheses/k-submodular.md` de danh dau individual-knapsack la mot nhanh rieng.
- Trong note 2025 journal, nhac ro paper nay la conference precursor, khong phai duplicate.

## Weaknesses / Limits

- Ban conference ngan nen nhieu chi tiet proof va ung dung bi nen.
- Chi cho monotone case, chua phan tich ro non-monotone.
- Query complexity co them yeu to `log(B)`, va paper van dua tren outer guessing loop.

## Research Ideas Triggered

- Tao comparison note giua total-knapsack va individual-knapsack trong `k`-submodular streaming.
- Theo doi xem phan nao cua proof that su dung pairwise monotonicity / orthant properties, phan nao la generic thresholding duoi nhieu budget.