# Wang 2025 - A 1/2-Approximation for Budgeted k-Submodular Maximization

## One-paragraph Summary

Day la paper combinatorial quan trong cho nhanh `budgeted k-submodular maximization` duoi mot rang buoc knapsack tong. Dong gop trung tam la chot cau hoi mo da ton tai vai nam: trong monotone `k`-submodular knapsack, chi can `1-Guess Greedy` la du de dat `1/2`, bang voi moc greedy duoi cardinality va matroid constraints. Cung mot khung cho non-monotone case cho ratio `1/3`. Diem moi that su khong nam o enumeration, ma o spine chung minh: thay vi discrete exchange / transformation chi hop khi hai nghiem co cung "kich thuoc", paper dua vao mot continuous transformation tu optimum sang greedy partial solution va dung `k`-multilinear extension chi de phan tich. Nho do paper vua cai thien approximation ratios cua dong `q`-guess greedy, vua giam enumeration tu `q = 4` xuong `q = 1`, va con mo rong sang mot loat bien the greedy / streaming khac.

## Classification Rationale

Paper thuoc `k-submodular` vi nghiem van la `k` tap roi nhau tren domain `(k+1)^V`, nhung bai toan cu the la `budgeted / knapsack` voi cost chung `c(e)` tren support. No nam dung giao diem giua ba line hien da co trong repo:

- oracle-model `k`-submodular maximization cua Ward-Zivny / Oshima;
- budgeted / streaming line cua Pham et al. 2022, DSAA 2022, Tang et al. 2022, Xiao et al. 2024;
- multilinear-extension line cua Zhou-Huang-Wang 2025.

Gia tri retrieval cua paper la no cho thay combinatorial greedy, neu duoc phan tich dung cach, da dat moc `1/2` cho monotone total-budget case ma khong can continuous optimization full-scale.

## Setup

- Domain / model: non-negative `k`-submodular function `f : (k+1)^V -> R_+`, voi `f(0) = 0`.
- Constraint: single knapsack constraint `c(x) <= B`, trong do `c(x)` la tong cost cua support.
- Objective classes: paper xu ly ca monotone va non-monotone.
- Access model: value oracle; moi buoc greedy chon cap `(e, j)` co marginal density `Delta_{e,j}(s) / c(e)` lon nhat.
- Baseline family: `q-Guess Greedy` enum tat ca feasible guesses co size `q`, roi chay density-greedy tu moi guess.

## Main Results

1. `1-Guess Greedy` dat `1/2` cho monotone k-submodular knapsack maximization.
2. Cung y tuong do dat `1/3` cho non-monotone case.
3. Query complexity cua `1-Guess Greedy` la `O(n^3 k^2)`, giam ro so voi `4-Guess Greedy` truoc do.
4. Dung decreasing-threshold cua Badanidiyuru-Vondrak, co the doi sang bien the `(1/2 - epsilon)` voi `~O(n^2 k^2)` queries trong monotone case.
5. Khung continuous transformation nay con cai thien nhieu algorithm da co:
   - `Greedy+Singleton` tu `0.273 / 0.219` len `1/3 / 1/4` cho monotone / non-monotone;
   - `Greedy+` tu `1/3 / 1/4` len `4/11` va `5/18`;
   - mot so semi-streaming algorithms tu `1/4 - epsilon` len it nhat `0.26 - epsilon` voi them mot pass.

## Core Algorithmic Idea

Thuat toan khong phuc tap: no chi la `q-Guess Greedy` voi `q = 1`.

- Thu enumerates moi singleton feasible `y`.
- Tu moi `y`, chay density-greedy: moi vong chon cap `(e, j)` co `Delta_{e,j}(s) / c(e)` lon nhat trong cac phan tu chua xet.
- Neu them `e` van feasible thi gan `e` vao nhan `j`; neu khong thi bo qua va tiep tuc.
- Tra ve nghiem tot nhat tren tat ca singleton guesses.

So moi cua paper la phan tich partial greedy solution `s` tai thoi diem dau tien ma greedy "reject" mot phan tu thuoc optimum vi budget khong con du. Partial solution nay chua nhat thiet la output cuoi, nhung no la diem neo dung cho continuous proof.

## Proof / Analysis Strategy

Spine proof co ba lop.

- Lop 1: `cost-equal key lemma`.
  Voi mot feasible solution `o`, neu greedy partial solution `s` co `c(s) = c(o)`, paper xay hai continuous processes:
  - `s(t)`: tang dan cac coordinate cua nghiem greedy theo toc do `1 / c(e)`;
  - `o(t)`: giam dan cac coordinate cua optimum theo toc do cung loai.
  Dat `x(t) = o(t) + s(t)`, khi do `x(0) = o`, `x(c(o)) = s`. Paper chung minh toc do mat gia tri `-F'(x(t))` khong vuot qua toc do tang gia tri cua greedy, trong do `F` la `k`-multilinear extension. Tich phan theo `t` cho ra:
  - monotone: `f(o) - f(s) <= f(s)`, nen `2 f(s) >= f(o)`;
  - non-monotone: pairwise monotonicity thay monotonicity, nen `f(o) - f(s) <= 2 f(s)`, suy ra `3 f(s) >= f(o)`.

- Lop 2: `cost-ratio lemmas`.
  Tu key lemma khi cost bang nhau, paper suy rong sang `c(s) = beta c(o)`:
  - monotone: `f(s) >= min(beta / 2, 1/2) f(o)`;
  - non-monotone: `f(s) >= min(beta / 3, 1/3) f(o)`.
  Y tuong la neu `beta <= 1` thi "keo dai" phan tu cuoi cua greedy de match cost ma van bao toan density order; neu `beta > 1` thi cat mot partial greedy solution co cost dung bang `c(o)`.

- Lop 3: `singleton guess absorbs the missing optimum`.
  Goi `o*` la optimum. Chon:
  - `y`: singleton gia tri lon nhat trong `o*`;
  - `z`: phan tu co cost lon nhat trong `o* \ y`;
  - `r = o* \ y \ z`.
  Khi `1-Guess Greedy` doan dung `y`, partial greedy solution `s` tai thoi diem reject dau tien thoa `c(s \ y) >= c(r)`. Ap dung cost-ratio lemma cho residual function `f_y` va residual set `r` de lay lower bound tren `f_y(s \ y)`. Phan gia tri con lai `f_{y sqcup r}(z)` duoc absorb boi singleton `y` vi `y` la singleton tot nhat trong optimum. Chinh decomposition
  `f(o*) = f(y) + f_y(r) + f_{y sqcup r}(z)`
  la buoc khoa ratio `1/2` va `1/3`.

## Key Techniques

- density-greedy sau mot singleton guess
- continuous transformation giua optimum va greedy partial solution
- `k`-multilinear extension dung chi cho analysis, khong dung trong algorithm
- derivative comparison argument thay cho discrete exchange
- cost-ratio reduction tu equal-cost lemma
- "guess highest-value singleton, charge highest-cost remainder separately" decomposition
- pairwise monotonicity de xu ly non-monotone case

## Key Lemmas Or Structural Claims

- Lemma 3.1: neu `c(s) = c(o)` trong monotone case thi `2 f(s) >= f(o)`.
- Lemma 3.2: neu `c(s) = beta c(o)` thi `f(s) >= min(beta / 2, 1/2) f(o)`.
- Theorem 3.3: `1-Guess Greedy` la `1/2`-approximation cho monotone kSKM.
- Lemma 4.1: non-monotone analogue cua key lemma, cho `3 f(s) >= f(o)` khi cost bang nhau.
- Lemma 4.2: non-monotone cost-ratio version, `f(s) >= min(beta / 3, 1/3) f(o)`.
- Theorem 4.3: `1-Guess Greedy` la `1/3`-approximation cho non-monotone kSKM.
- Proposition 5.1: `Greedy+Singleton` dat `1/3` monotone va `1/4` non-monotone.

## Delicate Points / Caveats

- Paper chi lam viec voi single knapsack co cost chung theo support. No khong giai quyet truc tiep setting label-dependent costs cua Pham et al. 2022.
- `1/2` la asymptotically tight theo lower bound unconstrained cua Iwata-Tanigawa-Yoshida, nhung paper tu chi ra rang voi `k` nho thi van co the co ratio tot hon; hien chua co algorithm nao vuot `1/2` ngay ca duoi cardinality.
- Continuous transformation o day la cong cu phan tich, khong phai multilinear-extension algorithm. Vi vay paper co gia tri thuc dung hon continuous algorithms query-nang.
- Buoc "replace the last greedy element by a stretched-cost surrogate while preserving marginal densities" la mot engineering trick trong proof; no khong phai thao tac tren nghiem discrete thuc te.
- Paper chu yeu phan tich diem reject dau tien cua mot phan tu optimum, khong phan tich truc tiep output cuoi cung. Neu doc nhanh rat de bo qua vai tro cua partial greedy solution nay.

## Extraction To Concepts

- Nen co concept note rieng cho `budgeted k-submodular maximization`, vi den luc nay repo da co nhieu paper total-budget, streaming, heterogeneous-cost, va individual-knapsack.
- Reusable ingredient moi: continuous transformation qua `k`-multilinear extension de phan tich greedy / greedy-plus algorithms khi hai nghiem co cost hay size khac nhau.
- Nen bo sung vao `concepts/k-submodularity.md` de danh dau rang knapsack line nay gio da co mot combinatorial `1/2` monotone result.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen danh dau paper nay la moc cho total-budget knapsack line, dat moc `1/2` / `1/3` bang combinatorial greedy.
- Phan recurring techniques cua synthesis nen them continuous transformation / multilinear-analysis-for-combinatorial-greedy.
- Open directions nen cap nhat theo paper: co vuot `1/2` duoc khong khi `k` nho, va co the day phuong phap nay sang heterogeneous costs hay multiple knapsacks khong.

## Weaknesses / Limits

- Khong xu ly multiple knapsacks, label-dependent costs, hay streaming in full.
- Query complexity `O(n^3 k^2)` van nang so voi cac streaming threshold methods, du da dep hon nhieu combinatorial `q`-guess papers truoc.
- Extension section chi phac thao mot so improvements; neu can dung lai cac ket qua `4/11`, `5/18`, hay `0.26 - epsilon` thi van nen doc ky paper goc lien quan.

## Research Ideas Triggered

- Viet comparison note rieng cho total-budget k-submodular line: Tang 2022 -> Pham 2022 -> DSAA 2022 -> Ha-Pham-Tran 2024 -> Xiao et al. 2024 -> Wang 2025 -> Zhou et al. 2025.
- Kiem tra xem continuous transformation nay co the ghep voi streaming thresholding de cho proof ngan hon hoac ratio tot hon khong.
- Kiem tra setting heterogeneous costs theo label: co the co mot analogue cua singleton-guess + residual charging khong.
- Tach rieng mot concept note ve "continuous transformations for greedy analysis" neu sau nay them du paper cardinality / matroid / knapsack cung dung spine nay.