# Metadata

- Title: Fairness in Monotone k-submodular Maximization: Algorithms and Applications
- Authors: Yanhui Zhu, Samik Basu, A. Pavan
- Year: 2024
- Venue: arXiv preprint (`arXiv:2411.05318v1`, November 8, 2024)
- Primary group: k-submodular
- Secondary tags: fairness, monotone, total-budget, lower-bounds, upper-bounds, thresholding, approximate-oracle
- Problem: monotone k-submodular maximization under a total budget together with lower and upper fairness bounds on each label / type
- Main guarantee: introduces a fairness-aware greedy algorithm with `1/3` approximation in `O(knB)` evaluations and a threshold-based algorithm with `(1/3 - epsilon)` approximation in `O((kn / epsilon) log(B / epsilon))`, plus robustness guarantees under approximate oracles
- Key techniques: extendability characterization for fairness-feasible partial solutions, fairness-aware greedy charging via transformed optima, lazy thresholding with a priority queue, and approximate-oracle variants
- Status: processed-deep
- Tags: #k-submodular #fairness #monotone #budget #thresholding #approximate-oracle
- Inbox source: inbox/2411.05318v1.pdf