# Fair K-Submodular Maximization

## Related Groups

- k-submodular
- mixed

## Type

- problem-setting
- technique-cluster

## Statement

Fair `k`-submodular maximization them rang buoc can bang giua cac nhan / labels vao bai toan `k`-submodular. Thuong moi nhan `i` co lower bound `l_i`, upper bound `u_i`, va co them mot rang buoc tong nhu total budget hoac matroid tren support.

## Intuition

Khac voi `k`-submodular thong thuong, mot partial solution khong chi can feasible hien tai ma con phai "de danh cho tuong lai" de van co the dat lower bounds cua cac nhan con thieu. Vi vay hai notion lap lai nhieu nhat la:

- `extendable`: partial solution van co the mo rong thanh nghiem fairness-feasible;
- `fairness approximation`: khi rang buoc qua kho, algorithm chi dam bao mot phan cua lower bounds.

## Main Regimes

- total budget + exact lower/upper bounds
- matroid + upper-only fairness
- matroid + lower/upper bounds nhung lower bounds chi dat xap xi
- monotone objectives
- non-monotone objectives
- exact oracle va approximate oracle

## Recurring Techniques

- extendability filtering trong greedy / thresholding
- transformed-optimum charging co kem fairness bookkeeping
- upper-only subroutine roi mo rong sang lower-bound problem
- random split cua lower-bound backbone
- induced matroids quanh partial fair solutions
- giam nhan cuoi cung ve mot bai toan submodular slice

## Related Results

- Zhu-Basu-Pavan 2024 cho thay duoi total budget, fairness exact van co the giu moc `1/3` cho monotone objectives, va thresholding dua query complexity tu `O(knB)` xuong `O((kn / epsilon) log(B / epsilon))`.
- Anonymous 2026 draft mo rong fairness sang matroid va non-monotone objectives, nhung phai danh doi lower bounds exact bang mot guarantee `floor(l_i / 2)`.
- So sanh hai ket qua tren cho thay fairness duoi total budget va duoi matroid la hai cap do kho khac nhau that su.

## Where It Is Used

- `2024-zhu-et-al-fairness-monotone-k-submodular-maximization`
- `2026-anonymous-fairness-k-submodular-matroid-constraint`