# Fairness in Monotone k-submodular Maximization: Algorithms and Applications

arXiv: https://arxiv.org/abs/2411.05318 · HTML: https://mlsanity.com/paper/2411.05318/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 32 references that are in the map.
- First posted on arXiv 8 Nov 2024.

## Builds on (most cited first, 5 of 5)

- [Fairness in Streaming Submodular Maximization: Algorithms and Hardness](https://mlsanity.com/paper/2010.07431/) (2020)
- [Data-Efficient Structured Pruning via Submodular Optimization](https://mlsanity.com/paper/2203.04940/) (2022)
- [Categorical Feature Compression via Submodular Optimization](https://mlsanity.com/paper/1904.13389/) (2019)
- [On maximizing a monotone k-submodular function subject to a matroid constraint](https://mlsanity.com/paper/1607.07957/) (2016)
- [Maximizing approximately k-submodular functions](https://mlsanity.com/paper/2101.07157/) (2021)

## Abstract (arXiv)

Submodular optimization has become increasingly prominent in machine learning and fairness has drawn much attention. In this paper, we propose to study the fair k-submodular maximization problem and develop a frac13-approximation greedy algorithm with a running time of O(knB). To the best of our knowledge, our work is the first to incorporate fairness in the context of k-submodular maximization, and our theoretical guarantee matches the best-known k-submodular maximization results without fairness constraints. In addition, we have developed a faster threshold-based algorithm that achieves a (frac13 - ε) approximation with O(fracknε log fracBε) evaluations of the function f. Furthermore, for both algorithms, we provide approximation guarantees when the k-submodular function is not accessible but only can be approximately accessed. We have extensively validated our theoretical findings through empirical research and examined the practical implications of fairness. Specifically, we have addressed the question: ``What is the price of fairness?" through case studies on influence maximization with k topics and sensor placement with k types. The experimental results show that the fairness constraints do not significantly undermine the quality of solutions.