# K-Submodularity

## Related Groups

- k-submodular
- mixed

## Type

- definition
- relation

## Statement

K-submodularity tong quat hoa submodularity sang setting `k` nhan / `k` thanh phan roi nhau. Bisubmodularity la truong hop `k = 2`, trong khi submodularity thuong duoc xem la moc co ban `k = 1`.

## Intuition

Thay vi quyet dinh mot phan tu co duoc chon hay khong, ta quyet dinh no nam trong "kenh" nao trong so `k` kenh. Day la ly do nhieu proof va algorithms phai thay doi so voi set-submodular case, du co chung linh cam greedy / diminishing returns.

## Equivalent Views

- generalization of bisubmodularity
- multi-label discrete diminishing-returns style structure

## Standard Examples

- bisubmodular functions
- k-submodular relaxations cua multilabel objectives voi nhan `0` dong vai tro undecided / unassigned
- Potts-energy relaxations va partial optimality preprocessing trong computer vision
- k-submodular maximization in value-oracle model
- unconstrained non-monotone k-submodular maximization via randomized assignment
- deterministic derandomization cua monotone randomized greedy
- monotone k-submodular maximization under knapsack / streaming constraints
- monotone k-submodular maximization under a matroid constraint
- k-submodular maximization under a matroid constraint with threshold-decreasing speedups
- monotone k-submodular maximization under per-coordinate cardinality constraints in streaming / online models
- online no-regret k-submodular maximization
- online / streaming constrained k-submodular maximization with budget-imbalanced parts
- monotone k-submodular maximization under total size constraints
- approximately k-submodular / noisy-objective maximization
- budgeted k-submodular maximization with label-dependent costs
- k-submodular maximization under individual knapsack constraints
- k-submodular maximization under individual size constraints
- k-submodular cover in weighted / streaming bicriteria settings
- fairness-aware k-submodular maximization with lower and upper bounds on each label
- private monotone k-submodular maximization under a matroid constraint
- continuous multilinear-extension approaches duoi knapsack / matroid / mixed constraints

## Related Results

- Huber-Kolmogorov 2013 dua ra Min-Max theorem va polyhedral viewpoint cho minimization, nhung polynomial-time oracle minimization van mo vi chua ro good characterization cua `P(f)`
- Gridchyn-Kolmogorov 2013 noi Potts partial optimality preprocessing voi `k`-submodular relaxations; trong subclass nay, parametric-maxflow preprocessing manh hon natural relaxation
- Hirai-Iwamasa 2016 cho characterization day du cua `k`-submodular relaxation qua closure duoi dual-discriminator `theta`, kem algorithm `O((kn)^2)`, half-integrality, va maximality trong binary case
- Hirai-Oki 2017 cho thay tap minimizers cua mot `k`-submodular function co the duoc ma hoa bang elementary PIP, nen khong gian partial optima co mot representation compact
- randomized greedy la ky thuat moc cho maximization
- can so sanh lien tuc voi unconstrained submodular maximization de hieu what transfers and what breaks
- trong unconstrained non-monotone line, Ward-Zivny va Iwata et al. dua ra khung randomized assignment, con Oshima 2021 lam sac phan tich local cua khung nay de day ratio vuot `1/2`
- Iwata-Tanigawa-Yoshida 2015 la moc can ban cho maximization: `1/2` unconstrained va `k / (2k - 1)` monotone, kem hardness asymptotic tight cho monotone
- Oshima 2017 derandomize duoc baseline monotone `k / (2k - 1)` bang cach duy tri mot phan phoi tren cac partial assignments va giai LP moi buoc
- Sakaue 2016 dua matroid vao line monotone combinatorial bang greedy `1/2`
- trong robust / noisy-objective line, Zheng et al. 2021 dinh nghia `eps`-approximately `k`-submodular va `eps`-ADR, trong do `eps`-ADR manh hon va cho greedy ratios dep hon
- trong per-coordinate cardinality streaming, Ene-Nguyen 2022 dung primal-dual va nguong dong theo tung label thay vi threshold guessing hay greedy nhieu pass
- trong online line, Soma 2018 dua offline randomized-greedy inequalities vao Blackwell approachability / OLO de dat no-`1/2` regret va no-`k / (2k - 1)` regret
- trong online / streaming constrained line rong hon, Spaeh-Ene-Nguyen 2025 dieu chinh he so threshold theo tung budget de xu ly budget imbalanced va mo rong sang non-monotone / knapsack
- sang setting knapsack / streaming, ky thuat chu dao chuyen tu label-randomization sang thresholding theo marginal-per-cost
- trong matroid-constrained line, Niu et al. 2023 cho thay threshold-decreasing co the giu ratios `(1/2 - epsilon)` va `(1/3 - epsilon)` ma bo duoc phu thuoc tuyen tinh vao rank cua greedy
- trong privacy line, Rafiey-Yoshida 2020 cho thay greedy / continuous-greedy duoi matroid co the duoc privatize bang exponential mechanism, van giu moc `1/2` cho monotone `k`-submodular
- trong continuous line, Huang-Wang-Zhou 2021 dinh nghia multilinear extension cho `k`-submodular va dat `1/2 - epsilon` / `1/3 - epsilon` cho single matroid hay `O(1)` knapsacks
- trong total-budget common-cost knapsack, Wang 2025 cho thay `1-Guess Greedy` da du de dat moc combinatorial `1/2` monotone va `1/3` non-monotone, bang mot continuous transformation qua `k`-multilinear extension
- voi total-budget budgeted k-submodular, khi chi phi phu thuoc label can randomization va expected analysis manh hon special case common-cost
- cover-side cua `k`-submodular mo them huong bicriteria streaming, noi voi `submodular cover` va `DR-submodular cover` nhung utility van song tren assignment domain
- fairness line dua lower / upper quotas vao tung nhan; duoi total budget co the giu fairness exact trong monotone case, con duoi matroid hien phai chuyen sang fairness approximation
- sang setting size constraints, threshold-greedy near-linear co the giu deterministic ratios `1/2 - epsilon` va `1/3 - epsilon` ma khong con phu thuoc tuyen tinh vao budget
- query-efficient streaming cho k-submodular can them machinery de xu ly cost, feasible truncation, va cach bracket OPT bang mot lower bound coarse
- individual knapsack la mot buoc tang do kho so voi total knapsack vi moi label co budget rieng va singleton / heavy-case phai duoc xet theo tung nguon
- trong common-cost single-knapsack line, corrigendum cua Tang-Wang-Chan nang ratio len `0.4`, Xiao et al. day tiep len `0.432` va them non-monotone `0.317`, truoc khi Wang 2025 chot moc `1/2` / `1/3`
- individual size constraints can mot exchange construction tinh te hon total size, vi khi doi item co the phai doi type truoc de giu budget cua tung label

## Where It Is Used

- `2013-gridchyn-kolmogorov-potts-parametric-maxflow-k-submodular`
- `2013-huber-kolmogorov-towards-minimizing-k-submodular-functions`
- `2014-ward-zivny-maximizing-k-submodular-functions`
- `2015-iwata-tanigawa-yoshida-improved-k-submodular-maximization`
- `2016-hirai-iwamasa-k-submodular-relaxation`
- `2016-sakaue-monotone-k-submodular-matroid-constraint`
- `2017-hirai-oki-pip-representation-k-submodular-minimizers`
- `2017-oshima-derandomization-k-submodular-maximization`
- `2018-soma-online-k-submodular-maximization`
- `2021-oshima-improved-randomized-k-submodular-maximization`
- `2020-rafiey-yoshida-private-submodular-k-submodular-matroid`
- `2021-zheng-et-al-maximizing-approximately-k-submodular-functions`
- `2021-tang-wang-chan-corrigendum-monotone-k-submodular-knapsack`
- `2021-huang-wang-zhou-optimal-k-submodular-multilinear-extension`
- `2022-ene-nguyen-streaming-monotone-k-submodular-cardinality`
- `2022-pham-et-al-budgeted-k-submodular-streaming`
- `2022-pham-et-al-fast-streaming-k-submodular-knapsack`
- `2023-nie-et-al-size-constrained-k-submodular-near-linear-time`
- `2023-niu-et-al-fast-k-submodular-matroid-constraint`
- `2023-wang-et-al-streaming-k-submodular-cover-problem`
- `2023-tran-et-al-k-submodular-individual-knapsack`
- `2023-xiao-et-al-k-submodular-knapsack-approximation`
- `2024-zhu-et-al-fairness-monotone-k-submodular-maximization`
- `2025-spaeh-ene-nguyen-online-streaming-constrained-k-submodular`
- `2025-tran-et-al-k-submodular-individual-knapsack-streaming`
- `2025-wang-budgeted-k-submodular-maximization`
- `2026-anonymous-fairness-k-submodular-matroid-constraint`