# Budgeted K-Submodular Maximization

## Related Groups

- k-submodular
- mixed

## Type

- problem-setting
- technique-cluster

## Statement

Budgeted `k`-submodular maximization tim mot nghiem `x in (k+1)^V` toi da hoa `f(x)` duoi rang buoc tong cost `c(x) <= B`. Khac voi set-submodular knapsack, moi phan tu duoc chon khong chi can "lay hay bo" ma con phai duoc gan vao mot trong `k` nhan roi nhau.

## Intuition

Dong nay kho hon set-submodular knapsack vi greedy decisions phai dong thoi xu ly:

- phan tu nao nen duoc lay;
- nhan nao cho phan tu do la tot nhat;
- va trong non-monotone / budgeted settings, mot local move tot theo density chua chac dung cho residual optimum.

Vi vay literature tach ra thanh nhieu nhanh:

- `q`-guess greedy combinatorial algorithms;
- threshold / streaming algorithms;
- multilinear-extension algorithms;
- va cac bien the moi cho individual knapsack hay heterogeneous label-dependent costs.

## Main Regimes

- total-budget, common-cost knapsack
- total-budget, label-dependent costs
- monotone objectives
- non-monotone objectives
- offline combinatorial greedy
- streaming / semi-streaming thresholding
- individual knapsack constraints theo tung label

## Recurring Techniques

- marginal-density greedy `Delta_{e,j}(s) / c(e)`
- singleton or small-seed guessing de absorb phan kho cua optimum
- thresholding theo marginal-per-cost
- coarse lower bound roi geometric threshold guessing
- heavy-vs-light cost partition
- pairwise monotonicity de giu non-monotone analysis
- continuous transformation qua `k`-multilinear extension khi can so sanh hai nghiem khac cost

## Current Ratios Visible In This Repo

- Tang-Wang-Chan 2022: monotone total-budget, `3`-guess greedy dat `0.316`, sau do duoc cai thien len `0.4`.
- Pham et al. 2022: streaming total-budget, common-cost dat `(1/4 - epsilon)` va heterogeneous-cost dat constant factor phu thuoc `beta`.
- Pham et al. 2022 (DSAA): monotone streaming total-budget, `1/10` single-pass va `1/4 - epsilon` multi-pass voi query complexity gan tuyen tinh theo `nk`.
- Ha-Pham-Tran 2024 va Xiao et al. 2024: combinatorial `q`-guess greedy ratios duoc day len khoang `0.4` va `0.432`.
- Wang 2025: `1-Guess Greedy` dat `1/2` cho monotone va `1/3` cho non-monotone, chot moc combinatorial dung voi support-constrained line.
- Zhou-Huang-Wang 2025: multilinear-extension route dat `(1/2 - epsilon)` va `(1/3 - epsilon)` cho monotone / non-monotone, va mo rong sang multiple knapsacks.

## Related Results

- Tong-total budget va individual-knapsack la hai line khac nhau that su; ky thuat cho line sau phai giu feasibility theo tung nhan, khong chi tong cost.
- Setting label-dependent costs khac ro ret common-cost case, vi marginal-density theo nhan khong con du de chon greedily mot cach sach.
- Wang 2025 cho thay phan tich continuous co the nang combinatorial greedy len dung moc `1/2` / `1/3` ma khong can continuous optimization toan phan.
- Zhou et al. 2025 cho thay multilinear extension con cho phep di qua broader constraints, nhung doi lai query complexity nang hon.

## Where It Is Used

- `2022-pham-et-al-budgeted-k-submodular-streaming`
- `2022-pham-et-al-fast-streaming-k-submodular-knapsack`
- `2023-tran-et-al-k-submodular-individual-knapsack`
- `2025-spaeh-ene-nguyen-online-streaming-constrained-k-submodular`
- `2025-tran-et-al-k-submodular-individual-knapsack-streaming`
- `2025-wang-budgeted-k-submodular-maximization`