# Metadata

- Title: Fairness k-submodular maximization subject to matroid constraint
- Authors: not listed in PDF (anonymous / blind draft)
- Year: 2026
- Venue: IJCAI 2026 draft suggested by filename; exact venue and authors to verify
- Primary group: k-submodular
- Secondary tags: fairness, matroid, monotone, non-monotone, approximation, relaxed-fairness
- Problem: fairness-aware k-submodular maximization under a matroid constraint, with both lower and upper per-label bounds and possibly non-monotone objectives
- Main guarantee: introduces `UFairkSub` for upper-bound-only fairness and then `FairkSub` for the full problem; for upper-only fairness it gets about `1 / 4.582 - epsilon` monotone and `1 / 6.494 - epsilon` non-monotone, and for the general fair problem it returns a matroid-feasible solution satisfying `floor(l_i / 2) <= |X_i| <= u_i` with ratios about `1 / 9.164 - epsilon / 2` monotone and `1 / 25.976 - epsilon / 4` non-monotone
- Key techniques: threshold-based upper-fair greedy, reduction of the last unfilled label to submodular matroid maximization, random splitting of a lower-bound backbone, and matroid-base exchange in the fairness analysis
- Status: processed-deep; venue-year-to-verify; anonymous-review-copy
- Tags: #k-submodular #fairness #matroid #non-monotone #monotone #approximation
- Inbox source: inbox/k_sub_matroid_ijcai26.pdf