Approximation Algorithms for k-Submodular Maximization Under the Fair Constraints and Size Constraints

Submodular function maximization, a crucial aspect of combinatorial optimization, is extensively applied in various fields like economics and computing. Recently, the focus has shifted towards the generalizations of submodular maximization problems, such as k-submodular function maximization. This approach not only considers the selection of elements from the ground set but also the specific k-set they belong to. It has been proved useful in modeling several machine learning problems, including influence maximization with k topics and sensor placement with k types of sensors. In real-world applications, elements possess certain attributes like gender, age, race, etc., which are used to group elements in the ground set. To maintain fairness, it is desirable to have a balanced number of elements in each group, introducing the concept of group fairness. We divide the ground set V into m groups \(\left( V_{1},V_{2},...,V_{m} \right) \) , each representing items with the same attribute. If the difference in the number of elements between any two groups is less than or equal to \(\alpha \) , we say the group fairness constraints are satisfied. Existing k-submodular algorithms do not account for the group fairness constraints, leading to imbalances in group sizes. This paper addresses this gap by studying k-submodular maximization under the fairness constraints. We explore the k-submodular maximization problem under the intersection of the fairness constraints and total size constraint, achieving an approximate ratio of 1/2 for monotone cases and 1/24 for non-monotone cases.