# K-Submodular Synthesis

## Core Papers

- `Towards Minimizing k-Submodular Functions` (Huber, Kolmogorov):
  paper nen tang cho minimization / polyhedral viewpoint; chung minh Min-Max theorem cho `k`-submodular functions, dinh nghia `P(f)`, va chi ro polynomial-time oracle minimization van mo.
- `Potts model, parametric maxflow and k-submodular functions` (Gridchyn, Kolmogorov):
  noi Potts partial optimality preprocessing voi `k`-submodular relaxation line; trong subclass Potts, parametric-maxflow cho preprocessing manh hon natural relaxation.
- `Maximizing Bisubmodular and k-Submodular Functions` (Ward, Zivny):
  paper moc trong inbox hien tai cho approximation algorithms trong oracle model.
- `Improved Approximation Algorithms for k-Submodular Function Maximization` (Iwata, Tanigawa, Yoshida):
  paper cot loi cua maximization line: dat `1/2` unconstrained, `k / (2k - 1)` cho monotone, va hardness asymptotic tight cho monotone case.
- `On k-Submodular Relaxation` (Hirai, Iwamasa):
  paper nen tang cho relaxability / persistency line; characterizes khi nao multilabel objective admit `k`-submodular relaxation, kem algorithm `O((kn)^2)`, half-integrality, va binary maximality.
- `On maximizing a monotone k-submodular function subject to a matroid constraint` (Sakaue):
  greedy combinatorial dau tien cho matroid-constrained monotone line, dat `1/2`.
- `A compact representation for minimizers of k-submodular functions` (Hirai, Oki):
  bo sung representation-level structural theory: minimizers tao elementary PIP / median semilattice, va Potts subclasses cho phep liet ke maximal minimizers.
- `Derandomization for k-submodular maximization` (Oshima):
  derandomize baseline monotone `k / (2k - 1)` bang distribution-support + LP.
- `No-regret algorithms for online k-submodular maximization` (Soma):
  mo nhanh online-learning branch voi no-`1/2` regret va no-`k / (2k - 1)` regret qua Blackwell approachability.
- `Improved Randomized Algorithm for k-Submodular Function Maximization` (Oshima):
  buoc cai thien quan trong cho unconstrained non-monotone line, day randomized assignment framework vuot moc `1/2`.
- `Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints` (Rafiey, Yoshida):
  mo them nhanh privacy / sensitive-data cho monotone `k`-submodular matroid, dat private `1/2` va sampled query reduction.
- `Maximizing Approximately k-Submodular Functions` (Zheng et al.):
  mo them robust / noisy-objective line, dinh nghia `eps`-approximately `k`-submodular va `eps`-ADR, kem greedy ratios duoi total-size va individual-size.
- `Corrigendum to "On Maximizing a Monotone k-Submodular Function under a Knapsack Constraint"` (Tang, Wang, Chan):
  corrigendum quan trong cho knapsack line; giu nguyen algorithm enumeration-size-2 + density-greedy nhung sua proof va nang ratio len `0.4`.
- `On Optimal Approximations for k-Submodular Maximization via Multilinear Extension` (Huang, Wang, Zhou):
  paper continuous / Frank-Wolfe cho multilinear-extension line, dat `1/2 - epsilon` va `1/3 - epsilon` cho single matroid hay `O(1)` knapsacks, va mo rong sang mixed intersections.
- `Streaming Algorithm for Monotone k-Submodular Maximization with Cardinality Constraints` (Ene, Nguyen):
  moc streaming / online primal-dual cho per-coordinate cardinality, giu mot nghiem feasible duy nhat va ratio tang theo `B_min`.
- `Maximizing k-Submodular Functions under Budget Constraint: Applications and Streaming Algorithms` (Pham et al.):
  paper budgeted / total-budget streaming tong quat cho cost chung va cost phu thuoc label, co ca monotone va non-monotone guarantees.
- `Fast Streaming Algorithms for k-Submodular Maximization under a Knapsack Constraint` (Pham et al.):
  buoc noi quan trong tu unconstrained maximization sang streaming / knapsack, voi constant approximation trong query complexity tuyen tinh theo `nk`.
- `Size-Constrained k-Submodular Maximization in Near-Linear Time` (Nie et al.):
  moc threshold-greedy offline cho total-size va individual-size, giu best-known deterministic ratios nhung bo duoc phu thuoc tuyen tinh vao budget.
- `Fast algorithms for k-submodular maximization subject to a matroid constraint` (Niu et al.):
  dua threshold-decreasing vao matroid-constrained line, giu moc `(1/2 - epsilon)` / `(1/3 - epsilon)` voi query complexity khong con phu thuoc tuyen tinh vao rank.
- `Maximizing a k-Submodular Maximization Function under an Individual Knapsack Constraint` (Tran et al.):
  conference precursor mo nhanh individual-knapsack cho `k`-submodular streaming.
- `Streaming Algorithms for the k-Submodular Cover Problem` (Wang et al.):
  mo nhanh cover-side cua `k`-submodular bang streaming bicriteria algorithms, bo sung mot doi xung voi submodular-cover va DR-submodular-cover line.
- `Approximation algorithms for k-submodular maximization subject to a knapsack constraint` (Xiao et al.):
  day knapsack line sang ca monotone va non-monotone combinatorial guarantees, dat `0.432` va `0.317` bang seed-enumeration + density-greedy.
- `Fairness in Monotone k-submodular Maximization` (Zhu, Basu, Pavan):
  paper mo nhanh fairness voi lower / upper quotas tren tung nhan duoi total budget, giu moc `1/3` va co threshold version `(1/3 - epsilon)`.
- `Online and Streaming Algorithms for Constrained k-Submodular Maximization` (Spaeh, Ene, Nguyen):
  framework rong cho monotone / general objectives duoi cardinality va knapsack, xu ly budget imbalanced va noi them sang partition-matroid submodular.
- `A 1/2-Approximation for Budgeted k-Submodular Maximization` (Wang):
  moc combinatorial moi cho total-budget knapsack, chot cau hoi mo ve `1/2` monotone bang `1-Guess Greedy`, dong thoi dat `1/3` cho non-monotone va dua continuous transformation qua `k`-multilinear extension vao phan tich greedy.
- `k-Submodular Maximization Under Individual Knapsack Constraints: Applications and Streaming Algorithm` (Tran et al.):
  journal extension day du hon cho nhanh individual-knapsack, co ca monotone va non-monotone discussion.
- `Fairness k-submodular maximization subject to matroid constraint` (anonymous draft):
  mo rong fairness sang matroid va non-monotone objectives, nhung phai danh doi lower bounds exact bang fairness approximation `floor(l_i / 2)`.

## Recurring Techniques

- reduction sang cac submodular slices `2^K` va base polyhedra
- tight-set analysis va closure duoi `sqcap`, `sqcup`
- unique-negative-leaf reduction ve local bisubmodular geometry
- unified vectors trong `k`-submodular polyhedron
- `k`-submodular relaxations va persistency cho multilabel energies
- closure duoi dual-discriminator `theta`
- greedy Fourier-Motzkin elimination cho he inequalities relaxation
- elementary PIP / median-semilattice representation cua tap minimizers
- randomized greedy
- bisubmodular-to-k-submodular generalization
- comparison voi submodular unconstrained maximization
- distribution-support derandomization bang LP extreme points
- Blackwell approachability + OLO cho online branch
- matroid basis exchange cho greedy constrained analysis
- refined local analysis cua randomized assignment framework
- primal-dual thresholding voi bien dual theo tung label
- threshold tuning theo tung budget label
- threshold greedy voi decreasing singleton-based thresholds
- exact-proxy transfer tu ham `k`-submodular exact sang objective xap xi
- marginal-per-cost thresholding
- continuous transformation qua `k`-multilinear extension de so sanh optimum va greedy partial solution khac cost
- multilinear extension + Frank-Wolfe continuous updates
- threshold-decreasing duoi matroid
- exponential mechanism tren cap `(e, i)` cho private greedy
- heavy-vs-light cost partition cho knapsack
- seed enumeration kich thuoc hang so de neutralize heavy items trong knapsack
- dung coarse lower bound de quet decreasing thresholds
- thresholding duoi nhieu budget labels
- type-swapping de giu feasibility duoi budget theo tung label
- free-disposal maintenance voi deque eviction
- randomization de xu ly label-dependent heterogeneous costs
- two-solution reduction cho non-monotone budgets mat can bang
- extendability filtering duoi fairness lower / upper bounds
- upper-fair subroutine + random backbone splitting cho fairness duoi matroid
- bicriteria streaming cover thresholding

## Main Problem Settings

- oracle-model minimization va exact Min-Max certificates
- polyhedral / structural theory qua `U(f)` va `P(f)`
- multilabel relaxations, persistency, va partial optimality
- compact representation cua tap minimizers
- lien he voi `k`-matroids / multimatroids
- value-oracle maximization
- bisubmodular special case
- approximation-ratio transfer / non-transfer tu submodular
- unconstrained non-monotone maximization voi improved randomized ratios
- deterministic monotone unconstrained maximization
- approximately `k`-submodular / noisy-objective maximization
- online no-regret maximization
- private monotone maximization duoi matroid
- per-coordinate cardinality streaming / online voi approximation tang theo `B_min`
- total-budget streaming voi cost co the phu thuoc label
- single-knapsack combinatorial approximation voi common costs va density-greedy
- total size constraints voi deterministic near-linear thresholding
- individual size constraints voi deterministic near-linear thresholding
- matroid-constrained maximization voi threshold-decreasing
- continuous multilinear-extension maximization duoi knapsack / matroid / mixed intersections
- monotone maximization duoi knapsack constraint
- streaming / multi-pass streaming khi query budget la tai nguyen chinh
- individual knapsack constraints theo tung label / source
- weighted cover trong streaming / bicriteria model
- fairness-aware maximization voi lower / upper quotas duoi total budget
- fairness-aware maximization duoi matroid, ke ca non-monotone objectives

## Open Directions

- can mot note rieng so sanh structural minimization / relaxation line `Huber-Kolmogorov -> Gridchyn-Kolmogorov -> Hirai-Iwamasa -> Hirai-Oki`
- can lam ro "good characterization" cua `P(f)` va vi sao no chan polynomial-time oracle minimization
- can so sanh potency cua ba cong cu persistency: natural relaxation, Kovtun preprocessing, va PIP representation cua tap minimizers
- can them cac paper tiep noi cho knapsack lineage de so sanh `O(n^4 k^3)` greedy, streaming `O(nk log n)`, va paper DSAA 2022 `O(nk)` / `O(nk / epsilon)`
- can mot note rieng so sanh unconstrained lineage `Ward-Zivny -> Iwata et al. -> Oshima derandomization -> Oshima improved-randomized`
- can mot note rieng so sanh primal-dual streaming `Ene-Nguyen` voi threshold-greedy `Nie et al.` cho cardinality / size constraints
- can mot note rieng cho online branch: offline randomized-greedy inequalities -> selection game -> Blackwell approachability -> online constrained variants
- can mot note rieng so sanh `budgeted total-budget` line (Pham et al.) voi `individual-knapsack` line (Tran et al.) va `individual-knapsack small items` appendix cua Spaeh-Ene-Nguyen
- can mot note rieng so sanh combinatorial knapsack line `corrigendum 0.4 -> Xiao 0.432 / 0.317 -> Wang 1/2 / 1/3` voi multilinear-extension line cua Huang-Wang-Zhou
- can mot note rieng so sanh total-size / individual-size threshold greedy voi knapsack / streaming thresholding
- can kiem tra xem co the vuot moc `1/2` trong total-budget case khi `k` nho hay khong; Wang 2025 neu ro cau hoi nay van mo ngay ca cho cardinality
- can thu xem continuous-transformation proof cua Wang co mo rong duoc sang label-dependent costs hay multiple knapsacks khong
- can mot note rieng so sanh fairness exact duoi total budget (Zhu et al. 2024) voi fairness approximation duoi matroid (anonymous 2026 draft)
- can kiem tra xem lower bounds co the giu exact duoi matroid va non-monotone objectives hay khong
- can mot comparison note cover lineage: submodular cover -> DR-submodular cover -> k-submodular cover
- can bo sung paper ve matroid, private, va continuous-greedy huong mo rong cua k-submodular
- can xem privacy line co mo rong duoc sang knapsack / streaming hay khong
- can xem robust / approximately-`k`-submodular line co mo rong duoc sang knapsack / matroid hay hoc tu du lieu hay khong
- can mot comparison note rieng total-knapsack vs individual-knapsack