Fairness k-Submodular Maximization Subject to Matroid Constraint

1 Introduction

Given a finite ground set V of size n, an integer k, and a non-negative (possibly non-monotone) k-submodular function f : (k+1)V →R+, where (k+1)V = {(X1, . . . ,Xk) | Xi ⊆ V ∀i ∈ [k],Xi ∩ Xj = ∅ ∀i ̸= j}. A k-set x = (X1, . . . ,Xk) ∈ (k+1)V is said to be fair if each component Xi satisfies the fairness bounds li ≤ |Xi| ≤ ui ∀i ∈ [k], for given lower and upper fairness bounds li and ui such that li ≤ ui. Given a matroid M over the ground set V , we study the problem of fairness k-submodular maximization under a matroid constraint, (denoted as FkSM): find a fair k-set x such that ⋃i Xi ∈ M that maximizes f (x).

This problem forms a fundamental optimization framework with broad applicability in artificial intelligence and machine learning, including revenue optimization and influence maximization [Ha et al., 2024; Ohsaka and Yoshida,

∗Corresponding author

2015; Qian et al., 2017; Spaeh et al., 2025], sensor placement [Ha et al., 2024; Nguyen and Thai, 2020], recommendation systems and image and document summarization [Spaeh et al., 2025; Feldman et al., 2018].

In the above applications, the fairness factor across components is essential for obtaining balanced and practically meaningful solutions. In recommendation systems [Spaeh et al., 2025; Mirzasoleiman et al., 2016], fairness constraints prevent the over-selection of items from a small number of genres, sellers, or product categories, thereby promoting diversity and improving user experience. Similarly, in revenue and influence maximization [Ha et al., 2024; Ohsaka and Yoshida, 2015; Nguyen and Thai, 2020], fairness ensures equitable representation across topics, which may correspond to demographic attributes such as gender, ethnicity, or region, and helps mitigate biased influence propagation. In sensor placement, fairness constraints balance the deployment of different sensor types, preventing excessive allocation to a single type and improving coverage quality, cost efficiency, and robustness of the sensing system [Nguyen and Thai, 2020; Ha et al., 2024].

Beyond fairness, the objective function in many realworld applications is inherently non-monotone. Such nonmonotonicity naturally arises in recommendation maximization, revenue maximization, and image summarization, where adding an element may reduce the overall utility due to redundancy or competition [Spaeh et al., 2025; Mirzasoleiman et al., 2016; Kuhnle, 2019; Pham et al., 2023]. While fairness k-submodular maximization has been extensively studied under simple cardinality constraints with monotone objectives [Zhu et al., 2024], the non-monotone setting remains largely unexplored.

Moreover, many practical constraints cannot be captured by cardinality limits and require more general feasibility models such as matroid constraints. Despite their broad applicability, no constant-ratio approximation algorithm is currently known for FkSM with general non-monotone objectives; consequently, the existence of provably guaranteed approximation algorithms for this problem remains a fundamental open question.

Our Contributions and Techniques. In this work, we address the above open question by developing constant-factor approximation algorithms for the FkSM problem. Our main contributions are summarized as follows (see Table 1).

We first study a special case of FkSM in which the lower fairness bounds satisfy li = 0 for all i ∈ [k], referred to as the Upper FkSM (UFkSM) problem. For this setting, we propose the UFairkSub algorithm, which achieves an approximation ratio of 1 4.582 -ϵ for monotone objective functions and 1 6.494 - ϵ for non-monotone objectives.

For the general FkSM problem with both lower and upper fairness bounds, we design the FairkSub algorithm that attains an approximation ratio of 1 9.164 - ϵ2 for monotone objectives and 1 25.976 - ϵ4 for non-monotone objectives, while allowing a factor 12 violation of the lower fairness bounds.

Finally, we conduct experiments to evaluate the performance of our algorithms on applications of the FkSM problem against state-of-the-art methods. The results show that, while remaining competitive in objective value, our algorithm substantially reduces the number of oracle queries and incurs only minimal fairness violations compared to other methods. Our techniques. It is worth noting that a recent approach to the fairness k-submodular maximization problem with monotone objectives relies on a greedy strategy over the space of extendable k-sets under simple size constraints [Zhu et al., 2024]. However, this approach critically depends on monotonicity and simple size constraints. To overcome this limitation, we propose a two-phase algorithmic framework together with a new theoretical analysis. Our framework, embodied in the FairkSub algorithm, is purely combinatorial and is designed to efficiently handle both monotone and nonmonotone objective functions under a matroid constraint.

In the first phase of our algorithm, we develop the UFairkSub algorithm as a core subroutine for generating candidate solutions to FkSM that satisfy only the upper fairness constraints, i.e., li = 0 for all i ∈ [k]. The algorithm employs a greedy threshold strategy to iteratively select elements and construct a solution s = (S1, S2, . . . , Sk), proceeding until exactly one component remains underfilled, namely when |Si| < ui for some i ∈ [k]. We further show that this construction can be combined with classical techniques for submodular maximization under matroid constraints to establish provable approximation guarantees. A key ingredient of this phase is a transformation that projects the optimal solution onto the algorithm's current solution at each iteration, allowing us to bound the loss relative to the optimum while preserving matroid feasibility. In the second phase, we refine the solution obtained from the first phase to achieve feasibility with respect to both upper and lower fairness bounds, as well as the underlying constraints. Specifically, we show how to combine the UFkSM to procedure systematically produce a final solution with provable guarantees. Our analysis exploits a structural decomposition of the optimal solution and key properties of matroids, together with a refinement mechanism that improves solution quality while controlling violations of the lower fairness bounds.

2 RelatedWork

k-submodular maximization. The notion of ksubmodularity was originally proposed by [Singh et al., 2012] and subsequently developed in a series of works that primarily concentrated on unconstrained k-submodular maximization [Ward and Zivn`y, 2014; Ward and Zivn`y, 2016; Iwata et al., 2016; Oshima, 2017; Soma, 2019]. [Ohsaka and Yoshida, 2015] first considered k-submodular maximization under a total size constraint B (denoted as kSMTS), requiring | ∪ki=1 Si| ≤ B, as well as under component size constraints B1,B2, . . . ,Bk (denoted as kSMIS), where |Si| ≤ Bi for all i ∈ [k]. The authors demonstrated that greedy-based algorithms achieve approximation ratios of 1 2 for the total size constraint and 1 3 for the component size constraints, respectively.

The kSMIS problem has further been studied in the nonmonotone setting. Specifically, [Spaeh et al., 2025] derived an approximation ratio of 0.3178 2 (1 - 1 mini Bi ) ≥ 18 , which asymptotically improves to 0.1589 as mini Bi → ∞. Beyond cardinality constraints, k-submodular maximization has been explored under general constraints. Under matroid constraints, [Sakaue, 2017] showed that a greedy algorithm attains a 1/2-ratio. The knapsack constraint was initiated by [Tang et al., 2022], who proposed a e-1 2e -approximation algorithm for monotone objectives. Subsequent work improved this guarantee to 12 for monotone objectives and 13 for non-monotone objectives [Ha et al., 2024; Zhou et al., 2025]. Among the most relevant works, [Zhu et al., 2024] studied fairness k-submodular maximization under total size constraint with monotone objective functions and obtained a 13 - approximation guarantee. Nevertheless, their method critically depends on monotonicity and cannot be extended to non-monotone objectives.

Submodular maximization under fairness constraint (SMF). This problem is the closest variant to FkSM, defined as follows: Given a submodular function f : 2V → R+ and a ground set V partitioned into k disjoint subsets V1, V2, . . . , Vk, the objective is to find a set S ⊆ V that maximizes f(S) subject to the fairness constraints li ≤ |S ∩Vi| ≤ ui, where li and ui denote the lower and upper fairness bounds of Vi. The study of the SMF was initiated by [Celis et al., 2018], who focused on monotone objectives and established a tight 1 - 1/e approximation guarantee via the continuous greedy paradigm. Later, [Halabi et al., 2020] examined a streaming formulation and derived approximation algorithms, achieving a 12 ratio in the monotone case and a 1 5.82 (1 - maxi li |Vi| ) ratio when the objective is nonmonotone. These guarantees were improved to γ3 , with γ denoting the best-known approximation ratio for submodular maximization under matroid constraints [Yuan and Tang, 2023]. Subsequent work has extended SMF to richer constraints, including matroid constraints [El Halabi et al., 2023; Halabi et al., 2024] and knapsack constraints [Cui et al., 2024]. However, these approaches only approximately satisfy the lower fairness bounds, typically guaranteeing |S ∩ Vi| ≥ ⌊li/2⌋, ∀i ∈ [k]. More recently, improved lower fairness guarantees have been achieved, i.e, |S ∩ Vi| ≥ ⌊(1 - ϵ)li⌋ though at the cost of approximation ratios depending on ϵ [Mahabadi et al., 2025]. Existing algorithmic techniques for SMF do not readily extend to kSMF for two fundamental reasons. First, k-submodularity exhibits structural properties that differ substantially from classical submodularity. Second, fairness constraints in kSMF are intrinsically more involved, as each element must be assigned to exactly one of the k components, rather than being selected from pre-defined partitions of the ground set. As a result, the existence of constant-factor approximation algorithms for the FkSM problem remains an open question.

3 Preliminaries

k-submodular notations. Given a finite set V of size n, and an integer number k, let [k] = {1, 2, . . . , k} and (k + 1)V = {(X1,X2, ...Xk) | Xi ⊆ V ∀i ∈ [k],Xi ∩Xj = ∅ ∀i ̸= j} be a family of k disjoint subsets of V . For simplicity, we call a tuple of k disjoint subsets as a k-set. For a k-set x = (X1,X2, . . . ,Xk), we call Xi the i-th component of x. For each e ∈ V , let x(e) = i if e ∈ Xi for some i ∈ [k], and 0 otherwise. We define supp(x) = ⋃i∈[k] Xi, denote (x)i = Xi for each i ∈ [k], and let |x| = ∑ki=1 |Xi|. Furthermore, if Xi = {e} and Xj = ∅ for all j ̸= i, we denote the corresponding k-set by ⟨e, i⟩. For e /∈ supp(x), adding e to Xi is denoted by x + ⟨e, i⟩. Similarly, if e ∈ Xi, then x - ⟨e, i⟩ denotes removing e from Xi in the k-set x.

Given two k-sets x = (X1, . . . ,Xk) and y = (Y1, . . . , Yk), we write x ⊑ y if Xi ⊆ Yi for all i ∈ [k]. The difference between x and y is defined as x - y = (X1 \ Y1, . . . ,Xk \ Yk). A function f : (k + 1)V → R+ is k-submodular iff

where x⊓y = (X1∩Y1, ..., Xk∩Yk), and x⊔y = (Z1, ...Zk) where Zi = Xi ∪ Yi \ (⋃j̸=i Xj ∪ Yj).

The function f is monotone if f(x) ≥ f(y), for all x ⊑ y. The marginal gain of adding e to the i-th set of x denote as ∆e,if(x) = f(x + ⟨e, i⟩) - f(x). We assume access to an oracle that returns f(x) for any queried k-set x.

Given lower and upper fairness bounds li and ui (with li ≤ ui for all i ∈ [k]). A k-set x = (X1, . . . ,Xk) ∈ (k + 1)V

is said to be fair if each component Xi satisfies li ≤ |Xi| ≤ ui ∀i ∈ [k].Without loss of generality, we assume that ui ≥ 1 for all i ∈ [k].

Matroids. Let V be a finite ground set. A collection of subsetsM⊆ 2V is said to define a matroid if it is non-empty and satisfies the following two properties:

• Downward-closedness: for any sets A and B with A ⊆ B, if B ∈ I, then A ∈M;
• Augmentation: for any A,B ∈Msuch that |A| < |B|, there exists an element e ∈ B \ A for which A ∪ {e} ∈ M.

For convenience, we use the notation A+e to denote A∪{e} and A - e to denote A \ {e}. A subset A ⊆ V is called independent if A ∈M. Throughout this work, we assume that the matroid is accessed via an independence oracle. All bases of a matroid have the same cardinality r, called the rank of the matroid.

Problem definition. In this work, we study fairness ksubmodular maximization under a matroid constraint (FkSM), which aims to find a fair k-set x satisfying ⋃i∈[k] Xi ∈ M that maximizes f(x).

We assume that there exists a feasible solution for the FkSM problem. The following Lemmas are useful for our theoretical analysis.

Lemma 1. [Ward and Zivn`y, 2014] f : (k + 1)V → R+ is k-submodular if and only if f satisfies the two following properties: (1) orthant submodularity, i.e. ∆e,if(x) ≥∆e,if(y) for any x, y ∈ (k + 1)V with x ⊑ y and e /∈ supp(y); (2) pairwise monotonicity, i.e. ∆e,if(x) + ∆e,jf(x) ≥ 0 for any x ∈ (k + 1)V , e /∈ supp(x) and i, j ∈ [k] with i ̸= j.

Lemma 2 ([Buchbinder et al., 2014]). Let f : 2V ↦→ R+ be submodular. Denote by A(p) a random subset of A of V where each element appears with probability at most p (not necessary independently). Then E[f(A(p))] ≥ (1 - p)f(∅).

Lemma 3 (Exchange property of matroid bases [Schrijver, 2003]). In any matroid, for any two bases B1 and B2 and for any partition of B1 into X1 and Y1, there exists a partition of B2 into X2 and Y2 such that both X1 ∪ Y2 and X2 ∪ Y1 are bases.

Lemma 4 (Feasibility of computing the rank of matroids [Schrijver, 2003]). A maximum-weight common independent set in two matroids can be found in strongly polynomial time.

We recall the submodular maximization under a matroid constraint (SMM), whose solution serves as a building block in our algorithmic design. Let f : 2V → R+ be a (possibly non-monotone) submodular function (corresponding to the case k = 1) 1 and a matroid M. The SMM problem is to find arg maxS∈M f (S).

4 Algorithm for UFkSM Problem

In this section, we first introduce the Upper Fair Approximation (UFairkSub) algorithm for the UFkSM problem, which serves as a key building block for computing solutions to the general FkSM problem.

1 A function f : 2V ↦→ R+ is submodular iff for any A ⊆ B ⊆ V and e ∈ V , f(A ∪ {e}) - f(A) ≥ f(B ∪ {e}) - f(B).

Given an instance (V, k, ui∀i ∈ [k],M) and a parameter ϵ > 0, the UFairkSub algorithm operates in a two-stage framework. In the first stage (Lines 1-10), it initializes the solution s ← 0, sets the set of unfilled components to I = [k], and computes the maximum singleton value M (Line 1).

The algorithm subsequently adopts a threshold-based greedy strategy to incorporate elements with large marginal contributions into s. Concretely, during each iteration of the while loop, every candidate element e is examined. If inserting e into the current solution preserves the feasibility of M, it determines ie ∈ I that maximizes the marginal gain of e. If the marginal gain is at least the threshold θ, e is assigned to component ie and added to the solution (Line 7). Once the component ie reaches its capacity, i.e, |(s)ie | = uie , it is removed from the set of available components I (Line 8). The threshold θ is initialized to M and is progressively reduced by a multiplicative factor of (1 - ϵ) in successive iterations, until it drops below 2ϵM/(3r). The first stage concludes either after all iterations are exhausted or when exactly one component remains unfilled, i.e., |I| = 1. Notably, this stage always selects pairs ⟨e, ie⟩ with non-negative marginal gain in to s due to the pairwise monotonicity of f. In particular, for any element e, there exist two distinct labels i, j ∈ [k] such that ∆e,if (s) + ∆e,j f (s) ≥ 0.

Algorithm 1: UFairkSub algorithm for UFkSM

Input: V, k, f,M, u1, . . . , uk, ϵ 1: s ← 0, I ← [k], s′ ← 0, θ ←M ← max e∈V, i∈[k] f(⟨e, i⟩), r = rank(M) 2: while θ ≥ 2ϵM 3r do 3: for e ∈ V \ supp(s) do 4: if supp(s) ∪ {e} ∈ M then 5: ie ← arg max i∈I ∆e,if(s) 6: if ∆e,ie f(s) ≥ θ then 7: s ← s + ⟨e, ie⟩ 8: If |(s)ie | = uie then I ← I \ {ie} 9: If |I| = 1 then break 10: θ ← (1 - ϵ)θ 11: if |I| = 1 then 12: i ← the only number in I 13: Define a matroid M′ = {S ⊆ V : S ∈M, |S| ≤ ui} 14: Define g : 2V →R+ as g(S) ← f (∑e∈S ⟨e, i⟩) 15: S ←Alg SMM (g, V,M′ ), s′ ← ∑e∈S ⟨e, i⟩ 16: break 17: x ← argmaxx′∈{s,s′ } f(x) 18: return x

If |I| = 1, say I = {i}, the algorithm moves into the Second stage (Lines 11-17): We first define a new matroid M′ = {S ⊆ V : S ∈ M, |S| ≤ ui} and adapts an 1/αapproximation algorithm for SMM problem for a submodular function g(S) ← f (∑e∈S ⟨e, i⟩) over ground set V and a matroid constraint M′ . Let S be the solution returned by the corresponding approximation algorithm, and define s′ := {⟨e, i⟩ | e ∈ S}. Finally, the algorithm outputs the better solution between s and s′ .

Theoretical Analysis. Denote ⟨ej, ij⟩ as the j-th pair added to s and t = |supp(s)| after the while loop of the Algorithm 1. Let sj = (⟨e1, i1⟩, ⟨e2, i2⟩, . . . , ⟨ej, ij⟩) represent the solution s after adding j ≤ t pairs.

Let o denote an optimal solution to the UFkSM problem. For each iteration j of the while loop in Algorithm 1, we define a transformation that produces a k-set oj satisfying the following properties: (1) |(oj)i| ≤ ui for all i, and (2) sj ⊑ oj . The transformation is defined as follows. For j = 0, set o0 = o. For j ≥ 1, we consider the following cases:

• If oj-1(ej) = ij, then set oj := oj-1.
• If oj-1(ej) = 0, set o′j := oj-1 +⟨ej, ij⟩. If |(o′j )ij | ≤ uij , then set oj := o′j . Otherwise, select an arbitrary element u ∈ (o′j )ij \ (sj)ij and set oj := o′j - ⟨u, ij⟩.
• If ij ̸= oj-1(ej) ̸= 0, let p := oj-1(ej) and set o′j := oj-1 - ⟨ej, p⟩ + ⟨ej, ij⟩. If |(o′j )ij | ≤ uij , then set oj := o′j . Otherwise, select an arbitrary element u ∈ (o′j )ij \ (sj)ij and set oj := o′j - ⟨u, ij⟩.

The transformation projects the optimal solution o onto the evolving solution sj. At each iteration, it retains sj as a fixed backbone while allowing oj to include additional elements within the given bounds. This alignment enables controlled synchronization between o and sj , which is key to establishing both approximation and fairness guarantees.

Lemma 5 ensures that the residual set Ej = supp(oj) \ supp(sj) is always a subset of the matroid-feasible set supp(o). This is crucial for proving that solutions is can be extended without violating matroid constraint.

Lemma 5. For each iteration j, define Ej = supp(oj) \ supp(sj). Then we have Ej ⊆ supp(o).

Lemma 6 establishes a per-iteration bound between the decrease in the value of the transformed solution oj and the marginal gain achieved by the constructed solution sj. This inequality enables a charging argument, where the loss of oj is paid for by the progress of sj , with constants depending on whether f is monotone or non-monotone. By summing over all iterations, the lemma directly links local improvements to a global approximation guarantee, thereby playing a central role in the overall analysis.

Lemma 6. For each j ∈ [t], the following holds:

• If f is non-monotone, then

• If f is monotone, then

Theorem 1. For any ϵ > 0, Algorithm 1 satisfies the following properties.

• For non-monotone objective functions f, the algorithm achieves an approximation ratio of 1 6.494 - ϵ.

• For monotone objective functions f, the algorithm achieves an approximation ratio of 1 4.582 - ϵ.
• Algorithm 1 runs inO( nk ϵ log r) +Q(Alg(SMM)), where Q(Alg(SMM)) denotes the query complexity of the underlying SMM algorithm used as a subroutine.

Proof. We first prove the approximation ratio for the case non-monotone functions f. Since st ⊑ ot, one can write ot = st ⊔ zr, where zr = {⟨z1, iz1 ⟩, ⟨z2, iz2 ⟩, . . . , ⟨zr, izr ⟩}, zi ∈ supp(ot) \ supp(st), izi = ot(zi), i ∈ [r]. Consider the following cases:

Case 1. If |st| = r, then r ≤ r. Since supp(st) ∈ M, it follows from the downward-closedness that supp(sr) ∈ M. By the augmentation property, there exists an ordering supp(z) = {z1, z2, . . . , zr} such that supp(si-1) + zi = {e1, e2, . . . , ei-1, zi} ∈ M, ∀i ≤ r. The algorithm always adds pairs with a non-negative marginal gain so f(st) ≥ f(sr), therefore

where (a) follows from the orthant submodularity of f, (b) holds since the pair ⟨zi, izi ⟩ was not selected into st in earlier iterations, and (c) follows from the selection rule of the pair ⟨e, i⟩ into si-1. On other hand, by Lemma 6, we obtain

From (1) and (2), we have

Case 2: If |st| < r, we consider the following cases: If |I| = 1 and i is the only number in I. From (2) we have:

By the properties of ot, we have (st)l = (ov)l, ∀l ̸= i and (st)i ⊑ (ot)i. By Lemma 3 supp(zr) = Et ∈ M and |zr| ≤ ui. Thus zr is a feasible solution of UFkSM problem. Since g is submodular, assuming 1/α be the approximation ratio of A for SMM, we have f(zr) ≤ αg(S) = αf(s′ ) and supp(s′ ) = S ∈ M. Therefore f(ot) = f(st ⊔ zr) ≤ f(st) + f(zr) ≤ f(st) + αf(s′ ). Put it into (3) we have f(o) ≤ (1 + 3 1-ϵ )f (st) + αf (s′ ) ≤ (α + 4-ϵ 1-ϵ )f (x). Therefore f(x) ≥ 1-ϵ α(1-ϵ)+4-ϵ f(o) ≥ 1-ϵ 4+α f(o). If |I| > 1, we assume that the algorithm continues the main loop until |I| = 1

or |supp(s)| = r. This is possible due to the pairwise monotonicity of the function f . Specifically, for each element e and the current solution x, there exist two distinct labels i, j ∈ [k] such that ∆e,if(x) + ∆e,jf(x) ≥ 0. Therefore, at least one label i ∈ {i, j} satisfies ∆e,if(x) > 0, which guarantees that the algorithm can make progress in each iteration and thus continue the main loop until |s| = r or |I| = 1. Let sT = (⟨e1, i1⟩, ⟨e2, i2⟩, . . . , ⟨eT , iT ⟩), T > t as s in this case. By the similarity argument of Case 1 and Case 2 with |I| = 1, we have f(sT ) ≥ 1-ϵ 4+α f(o). We have

f(sT ) - f(st) ≤ ∑e∈supp(sT )\supp(st) ∆e,sT (e)f(st) (d) ≤ 2ϵM 3r ≤ 2ϵ 3 f(o), where (d) holds since the marginal gain of each additional pair is smaller than the final threshold 2ϵM/(3r). This implies that f(st) ≥ f(sT ) - 2ϵ 3 f(o) ≥ ( 1 4+α - ϵ)f(o). Combining all cases, we obtain an approximation ratio of 1 4+α - ϵ. By instantiating the best-known approximation algorithm for SMM with α = 1 0.401 [Buchbinder and Feldman, 2024], the approximation ratio becomes 1 6.494 - ϵ. The proof of the ratio for monotone functions and query complexity are presented in the appendix.

5 Algorithm for General FkSM Problem

We now present a novel algorithmic framework, denoted by FairkSub (Algorithm 2), for the FkSM problem. The framework illustrates how the previously proposed UFairkSub algorithm can be systematically adapted as a key subroutine to achieve the desired theoretical guarantees. Consequently, the resulting algorithm has a more intricate structure and adopts a two-phase strategy to construct solutions while rigorously enforcing the required bound guarantees.

Given an instance of FkSM with parameter ϵ, the algorithm proceeds in two stages. In Phase 1, the algorithm first computes a maximum-cardinality independent set L ∈ M, which can be obtained in polynomial time (Lemma 4) and satisfies |L| = r ≥ ∑i∈[k] li. It then adapts UFairkSub to compute a candidate solution u for UFkSM on the restricted ground set L, subject to upper fairness bounds li and a matroid constraint that is reduced to a cardinality constraint of size ∑i∈[k] li. For each component i of u, the set (u)i is filled with li elements (Line 5). The algorithm then randomly splits u into two solutions, u(1) and u(2) , such that each component (u(j) )i has size ⌊li/2⌋ (Line 6). The algorithm continues adapting UFairkSub twice to find candidate solutions x(j) , j ∈ {1, 2} under the following constraints: upper fairness bounds ui, an induced matroid of M defined by supp(u(j) ) as Mj = {T ⊆ V : T ∪ supp(u(j) ) ∈ M}. This step yields a potential solution x(j) satisfying all upper fairness constraints while remaining improvable (Line 8).

In Phase 2, the algorithm initializes y(j) ← x(j) and then refines the solution by selectively adding elements to any component i from (u(j) )i satisfying |(y(j) )i| < ui, with the dual objectives of (1) enhancing satisfaction of the lower fairness bounds and (2) ensuring a provable bounded guarantee on the quality of the resulting solutions y(j) . By construction, this process always preserves matroid feasibility, due to the definition of the induced matroids Mj and the construction of u(j) . Finally, the algorithm outputs the best solution among all candidates {y(1) , y(2) , u}. We present the theoret-

Algorithm 2: FairkSub algorithm for FkSM

Input: V, k, f, li, ui, ∀i ∈ [k], M, ϵ // Phase 1: Initializing solution under upper fairness bounds 1: L← argmaxS⊆V,S∈M |S|, u(1) ← 0, u(2) ← 0 2: u←Adapt UFairkSub with upper bounds li andM is size constraint ∑i∈[k] li 3: for i ∈ [k] do 4: if |(u)i| < li then 5: Randomly select li - |(u)i| elements from L \ supp(u), assign them to (u)i, and remove them from L 6: Uniformly at random select 2⌊ li 2 ⌋ elements from (u)i and divide them evenly into two subsets (u(1) )i and (u(2) )i 7: Define matroids Mj = {T ⊆ V : T ∪ supp(u(j) ) ∈M}, j ∈ {1, 2} 8: x(j) ← UFairkSub(V, f, k, f, u1, . . . , uk,Mj, ϵ) // Phase 2: Solution refinement under fairness bounds 9: for j ∈ {1, 2} do 10: y(j) ← x(j) 11: for i ∈ [k] do 12: foreach e ∈ (u(j) )i do 13: If |(y(j) )i| < ui then y(j) ← y(j) + ⟨e, i⟩ 14: s ← argmaxx∈{y(1) ,y(2) ,u} f(x) 15: return s

ical guarantees stated in Theorem 2.

Theorem 2. For any ϵ > 0, the following statements about Algorithm 2 hold.

• It returns a solution s that satisfies supp(s) ∈ M and ⌊ li 2 ⌋ ≤ |(s)i| ≤ ui for the FkSM problem.
• For non-monotone functions f, it attains an approximation ratio of 1 25.976 - ϵ4 .
• For monotone functions f , the algorithm achieves an approximation ratio of 1 9.164 - ϵ2 .
• Algorithm 1 runs in O ( nk ϵ log r) + Q(Algorithm for SMM), where Q(Algorithm for SMM) denotes the query complexity of the underlying SMM algorithm used as a subroutine.

Proof. The approximation ratio is obtained by splitting the optimal solution o into two k-sets and using the matroid base exchange property to transform them into feasible subproblem solutions. Applying UFairkSub to these subproblems and aggregating the results yields the claimed guarantee.

L1 ∪ supp(o1) ∈ M and L2 ∪ supp(o2) ∈ M, where L1 = supp(u(1) ) and L2 = supp(u(2) ). This implies that each oj is a feasible solution to the UFkSM problem with instance Ij = (f, V, u1, . . . , uk,Mj) for j ∈ 1, 2. Let ρ denote the approximation ratio of UFairkSub. After Line 8 of Algorithm 2, we have

For the case where f is non-monotone. For any k-set v ∈ (k +1)V that supp(v) = {v1, v2, . . . , vm}, we define a finite ground set T(v) = {⟨v1, v(v1)⟩, . . . , ⟨vm, v(vm)⟩}, where each pair ⟨vi, v(vi)⟩ is treated as an individual element of T(v). We then define a function h(·) : 2T(v) ↦→ R+ by h(T(v′ )) = f(v′ ) for any v′ ⊑ v. By the orthant submodularity of f, it follows that h is a non-negative and submodular function. For j ∈ {1, 2}, consider the function h′ (·) = h(T(x(j) ) ⊔ ·), h′ is also non-negative and submodular function. Denote u′(j) ⊑ u(j) as a k-set that contains all pairs added into y(j) in for loop (Lines 9-14). By the construction of u(j) in Algorithm 2, for any pair ⟨e, i⟩ ⊑ u′(j) :

Applying Lemma 2 gives

By the selection of final solution, we obtain

This implies the approximation ratio ρ4 = 1 25.976 - ϵ4 . For the case where f is monotone, since x(j) ⊑ y(j) , we have f(y(j) ) ≥ f(x(j) ), and hence the approximation ratio is ρ2 = 1 9.164 - ϵ2 . The proof for the fairness bounds and the query complexity can be found in the appendix.

6 Experimental Evaluation

In this section, we conduct comprehensive experiments to demonstrate the performance of our FairkSub algorithm 2 on three representative applications of the general FkSM problem, namely Max-k-Cut (MkC), k-topic Influence Maximization (kTIM), and k-measurement Sensor Placement (kMSP). We set up a partition matroid (a special case of a matroid) in our experiments, following prior study [El Halabi et al.,

2 The code of our algorithm is available at https://github.com/ tantdhvan/kSubFairMatroid.

2023]. We parameterize the fairness constraint by a budget ratio B ∈ (0, 1]. Specifically, we set the cardinality budget to b = ⌊B|V |⌋, and define the fairness bounds for each label i ∈ [k] by li = ⌊0.8 bk ⌋ , ui = ⌊1.4 bk ⌋ , ∀i ∈ [k]. In all figures, B is reported on the horizontal axis; accordingly, B serves as the control parameter of the fairness constraint. Since the FkSM problem has not been explicitly studied in prior work, we compare our approach with the most closely related state-of-the-art algorithms. FairGreedy: a traditional

greedy algorithm that iteratively selects the pair with the highest marginal gain while satisfying both the matroid and fairness constraints. This approach is commonly used for general k-submodular maximization and has been adopted in recent works [Ohsaka and Yoshida, 2015; Zhu et al., 2024]. kGreedyIS: the algorithm for k-submodular maximization under individual size constraints [Ohsaka and Yoshida, 2015]. kGreedyTS: the algorithm for k-submodular maximization under a total size constraint [Ohsaka and Yoshida, 2015].

To adapt kGreedyIS and kGreedyTS to our problem setting, we proceed as follows: (i) we first construct a maximumsize feasible solution satisfying the matroid constraint; (ii) we adapt kGreedyIS by treating the upper fairness bounds as individual size constraints; and (iii) we adapt kGreedyTS by setting the total size constraint to B. These adapted algorithms serve as heuristic baselines and do not provide any theoretical approximation guarantees. We evaluate all algorithms using four criteria: (i) objective value, (ii) number of oracle queries, (iii) running time, and (iv) fairness error FairErrors(x) = ∑i∈[k] max{|(x)i| - ui, ; li - |(x)i|; 0}, as adopted in [Zhu et al., 2024]. Due to page limitations, detailed experimental settings and matroid specifications are deferred to the appendix.

Experimental results. We report the main results (Fig. 1) for two representative scenarios: (i) MkC (ii) the kTIM on Amazon and Facebook datasets. More detailed results are included in the appendix.

Objective value. Fig. 1(a,d) shows that FairkSub provides stable solution quality as B increases. On Amazon (MkC), FairkSub achieves objective values close to FairGreedy (a gap of about 5%), while it clearly outperforms kGreedyIS and kGreedyTS (about 36.9%-85.0% higher than kGreedyIS, and 37.0%-69.0% higher than kGreedyTS). On Facebook, FairkSub remains competitive with FairGreedy, while consistently outperforming kGreedyIS by about 0.7%- 7.6% and substantially surpassing kGreedyTS by approximately 12.2%-31.8%. Number of queries. Fig. 1(b,e) highlights the query efficiency of FairkSub, especially for MkC. On Amazon, FairkSub reduces the number of queries by about 79-278 times compared to FairGreedy, and by about 35-93 times compared to kGreedyIS/kGreedyTS. On Facebook, the reduction is more moderate: compared to FairGreedy, FairkSub uses about 1.3-3.7 times fewer queries; compared to kGreedyIS, FairkSub uses fewer queries when B ≥ 0.04 (about 1.3-1.7 times fewer), while at B = 0.02 it may require more queries. Fairness Errors. Fig. 1(c,f) indicates that FairkSub generally controls the fairness constraints well. On Amazon, FairkSub attains FairErrors = 0 for most cases B and only shows a very small violation at B = 0.5 (FairErrors = 17), whereas kGreedyTS has substantial violations that grow with B (e.g., 350 → 1366), and kGreedyIS/FairGreedy may also violate fairness at larger B. On Facebook, FairkSub keeps fair error equal to 0 for all tested B, matching FairGreedy/kGreedyIS, and improving over kGreedyTS (whose violations increase from 72 to 534 as B grows). Overall, the results suggest that FairkSub strikes a good balance between solution quality and computational cost: while remaining competitive in objective value, FairkSub substantially reduces the number of queries, and

(c)

(f)

Figure 1: Performance of the algorithms in terms of objective value, query complexity, and fairness error.

7 Conclusions

We studied the FkSM problem with possibly non-monotone objectives, which has broad significance and impact in artificial intelligence and machine learning. Our combinatorial two-phase framework provides the first constant-factor approximation guarantees while ensuring matroid feasibility, full upper-bound satisfaction, and a 1/2 factor guarantee on the lower bounds. Experiments on standard benchmark datasets further demonstrate the effectiveness of our approach in terms of solution quality, query efficiency, and running time. An important direction for future work is to extend this framework to richer and more general constraint settings.

Acknowledgments

This research was supported by the National Foundation for Science and Technology Development (NAFOSTED), Vietnam, under grant number 102.01-2025.19.