Fair Submodular Maximization over a Knapsack Constraint

1 Introduction

Submodular maximization is a fundamental problem in artificial intelligence and computer science, with continuous research since the 1970s [Cornuejols et al., 1977; Nemhauser and Wolsey, 1978]. The problem involves selecting a subset of elements from a given set to maximize a submodular function defined over them. It captures a wide range of tasks across various domains, such as clustering [Anegg et al., 2020; Backurs et al., 2019; Chierichetti et al., 2017], feature selection [Amiridi et al., 2021; Bao et al., 2022; Yu et al., 2016], movie recommendation [Avdiukhin et al., 2019; Dutting et al., 2022; Haba et al., 2020], and so on. However, recent studies [Celis et al., 2018; Halabi et al., 2023] have found that in some data mining applications, traditional submodular optimization algorithms may face a fairness issue.

The elements in the practical dataset often come from different groups (e.g., people of varying ages or genders [Halabi et al., 2023; Halabi et al., 2020; Wang et al., 2021]), but traditional algorithms do not account for this factor, leading to an imbalance in the number of selected elements from each group.

To address this issue, [Celis et al., 2018] introduces a group fairness notion into submodular maximization. Specifically, assuming that all given elements are partitioned into several groups, a solution is considered fair if the number of selected elements from each group falls within a specified range. One of their results is incorporating this group fairness notion into the classic cardinality-constrained submodular maximization problem, which aims to select at most k elements that satisfy the fairness constraints and maximize the submodular objective. They employ a well-known relax-and-round framework [Calinescu et al., 2011] in submodular maximization that first applies continuous greedy to obtain a fractional solution and then designs a randomized rounding procedure to produce an integral solution. They show that a tight approximation ratio of (1 - 1/e) can be obtained in expectation by a relax-and-round approach.

In this paper, we explore a generalized version of the above model. Note that in many applications [Kempe et al., 2003; Krause et al., 2008; Lin and Bilmes, 2011], submodular maximization is often subject to a more general knapsack constraint rather than a simple cardinality limit, where each element has an associated weight, and the total weight of the selected elements must not exceed a specified budget. Therefore, we focus on optimizing fair solutions under a knapsack constraint. This general constraint introduces new challenges to fair submodular maximization. Selecting elements requires simultaneously balancing their weights, group memberships, and contributions to the submodular objective.

We notice that a recent study [Cui et al., 2024] also considers this generalized model. They focus on the streaming scenario and demonstrate that if fairness constraints are allowed to be violated by a factor of 1/2, a two-pass streaming algorithm can achieve a constant approximation. Furthermore, we find that directly extending the algorithm from [Celis et al., 2018] to this general problem returns a (1 - 1/e)- approximation fair solution, but at the cost of violating the knapsack constraint. Nevertheless, to the best of our knowledge, whether a non-trivial approximation exists when both fairness constraints and the knapsack constraint must be strictly satisfied remains an open problem.

1.1 ProblemDefinition and Challenges

The problem of fair knapsack-constrained submodular maximization (FKSM) is formally defined as follows. There is a ground element set E = {e1, . . . , en} and a monotone submodular 1 function f : 2E → R defined over them. Each element e ∈ E has a weight we and an associated color δe. Let group Gi represent the set of elements of color i, and G = {G1, . . . ,Gk} be the collection of all groups. Each group Gi ∈ G is associated with an interval (li, ui]. The goal is to select an element subset S ⊆ E to maximize the value of the function f, while ensuring that the total weight of the selected elements does not exceed a given budget B, i.e., w(S) := ∑e∈S we ≤ B, and that the number of selected elements from each group Gi lies within the range (li, ui], i.e., li < |S ∩ Gi| ≤ ui. We call the former the knapsack constraint and the latter the fairness constraints.

We refer to a special case of our model where the weight of each element is 1, i.e., the knapsack constraint simplifies to a cardinality constraint, as FKSM. Similarly, we refer to another special case of our model where li = -∞, i.e., there is no lower bound on the number of elements selected from each group, as FKSM. These two special cases represent specific simplifications of the knapsack constraint and the fairness constraints, respectively. Both of them have been extensively studied in the literature [Celis et al., 2018; Gu et al., 2023] and can achieve a (1-1/e-ϵ)-approximation for any ϵ > 0 using the relax-and-round framework. The framework involves two steps: first, applying the continuous greedy algorithm to generate a fractional solution {xe ∈ [0, 1]}e∈E that satisfies the constraints and achieves an approximation ratio of (1 - 1/e); and second, employing randomized pipage rounding to produce a feasible integral solution {ye ∈ {0, 1}}e∈E.

However, things become more challenging when both constraints-the knapsack and fairness constraints-are enforced without simplification, as prior methods are no longer applicable. While the first step of continuous greedy can still generate a fractional solution that meets the constraints, the second step of randomized pipage rounding encounters feasibility issues. The main complication with the knapsack constraint lies in the varying weights of the elements. Randomized pipage rounding can only guarantee that the number of selected elements remains unchanged (i.e., ∑e ye = ∑e xe), but cannot strictly enforce the total weight constraint. This limitation explains why the problem becomes simpler in FKSM , where all element weights are uniform.

On the other hand, although randomized pipage rounding cannot strictly enforce the total weight constraint, it does ensure that the expected total weight satisfies the constraint: E[∑e weye] ≤ B and the y variables are negatively correlated. Using standard knapsack enumeration techniques [Chekuri et al., 2009], it can be shown that, with high probability (w.h.p.), ∑e weye ≤ (1 + ϵ)B for any ϵ > 0. This result implies that we can scale the knapsack size down by a factor of (1 + ϵ) to B′ = B/(1 + ϵ), run the algorithm on the scaled instance, and obtain an integral solution that w.h.p. satisfies the original knapsack constraint: ∑e weye ≤ (1 + ϵ)B′ = B. This knapsack scaling approach works well for FKSM , as the simplified fairness constraints exhibit a down-closed property and slightly reducing the knapsack size only has a minor impact on the optimal objective. However, in the general FKSMproblem, reducing the knapsack size even slightly may render the instance infeasible. For example, consider an instance where the knapsack capacity is just sufficient to satisfy the lower bounds in fairness constraints. Any further reduction in capacity would result in the absence of feasible solutions, highlighting a critical challenge in handling both knapsack and fairness constraints simultaneously in the general FKSM setting.

1 A function f : 2E → R is submodular if for all A,B ⊆ E we have f(A) + f(B) ≥ f(A ∩ B) + f(A ∪ B); or equivalently f(A ∪ e) - f(A) ≥ f(B ∪ e) - f(B) for all A ⊆ B ⊆ E and e ∈ E. The function is monotone if f(A) ≤ f(B) for all A ⊆ B.

1.2 Our Techniques and Results

This work makes progress in finding a non-trivial approximation for FKSM. To overcome the challenges mentioned above, we propose a novel technique: knapsack truncating and combine it with the randomized weighted pipage rounding. The knapsack truncating technique can reduce an FKSM instance I to an FKSM instance ¯ I (with the same ground elements and objective function) that satisfies the following two desirable properties:

• Optimality Inheritance: There exists an optimal solution of I that remains feasible for ¯ I.
• Feasibility Extension: For any feasible solution ¯ S of ¯ I, there always exists a feasible solution S of I such that f (S) ≥ f (S′ )/2.

When the number of groups is constant, the reduction can be performed in polynomial time. Therefore, leveraging this technique and the algorithm for the FKSM problem, we have the following:

Theorem 1.1. Given an FKSM instance with a constant number of groups, there exists a polynomial-time algorithm that achieves an approximation ratio of 12 (1 - 1e ) - ϵ with probability at least 1- 1e - 1 e2 for any ϵ > 0.

The other technique is a generalization of randomized pipage rounding, referred to as randomized weighted rounding. The randomized weighted rounding technique has already been applied to additive objective function cases in many previous works [Aziz et al., 2024; Gandhi et al., 2006]. During this process, the weights of the elements are taken into account to guide the rounding. This method ensures that the total weight remains unchanged before and after rounding. Additionally, for each element e, it guarantees that E[ye] = xe, where xe represents the fractional solution, and ye denotes the rounded solution. We extend this technique to the submodular function case and prove that all properties of pipage rounding (e.g., negative correlation, objective concentration) still hold in randomized weighted pipage rounding (Section 4.3), which might be useful for other problems. By integrating this technique with the continuous greedy method, we have the following:

Theorem 1.2. Given an FKSM instance, if the fairness constraints are relaxed to be satisfied in expectation, there exists a polynomial-time algorithm that returns a solution with an expected approximation ratio of (1 - 1e ) - ϵ for any ϵ > 0.

The above theorem shows that when the fairness constraints are relaxed to require expected satisfaction, an approximation ratio of 1 - 1/e - ϵ can be achieved in expectation. As mentioned earlier, the method from [Celis et al., 2018] can be easily extended to FKSM. It guarantees a fair solution with an expected approximation ratio of 1 - 1/e - ϵ while ensuring the knapsack constraint is satisfied in expectation (a detailed proof is provided in [Li et al., 2025]). Therefore, we can conclude that if either the knapsack or fairness constraint is relaxed to require only expected satisfaction, a tight approximation ratio of 1 - 1/e - ϵ can be achieved.

1.3 Other RelatedWorks

Group fairness in submodular maximization has recently attracted considerable attention. Various research efforts have embraced the group fairness model, suggesting fair submodular maximization algorithms that operate under a range of constraints. These include the matroid constraint, applied in both streaming and offline settings [Halabi et al., 2023; Halabi et al., 2020; Halabi et al., 2024]. Fair submodular maximization subject to a knapsack constraint is recently proposed by [Cui et al., 2024] under the streaming setting. Without fairness, the problem just aims to maximize a monotone submodular function subject to a knapsack constraint, which admits a (1- 1e )-approximation algorithm [Sviridenko, 2004]. [Kulik et al., 2009] studies submodular maximization subject to a constant number of linear constraints and gives a (1 - 1e - ϵ) approximation algorithm. Further, if the fairness constraint only has an upper bound, then the problem becomes the submodular maximization subject to a knapsack and partition matroid constraint. A batch of works studies the intersection with p-matroid and q-knapsacks [Chekuri et al., 2014; Feldman et al., 2023; Gu et al., 2023; Lee et al., 2009; Mirzasoleiman et al., 2016]. The current best algorithm is Ω(1/(p + q))-approximation, which is given by [Gu et al., 2023].

We also notice that a closely related work is the deterministic weighted pipage rounding proposed by [Ageev and Sviridenko, 2004] for the max-coverage problem with knapsack constraint. They show that the weighted pipage rounding algorithm returns a (1- 1e -ϵ)-approximate solution. However, since their rounding method is deterministic, it cannot be directly applied to ensure fairness in our problem. In our technique, a randomization procedure is introduced, which enables us to maintain the fairness constraint in expectation, and demonstrates that the produced random variables are wellconcentrated.

1.4 Roadmap

Section 2 states some terminology and prior results. In Section 3, we introduce the knapsack truncating technique and present a constant approximation algorithm for FKSM strictly respecting knapsack and fairness constraints when the number of groups is constant. In Section 4, we consider the scenario where fairness constraints are allowed to be satisfied in expectation and show that a constant approximation can be achieved by a randomized weighted pipage rounding approach. The paper finally concludes in Section 5.

2 Preliminaries

In this section, we introduce some terminology and prior results that will be used throughout this paper. A fractional vector x = {xe ∈ [0, 1]}e∈E is called a fractional solution of an FKSM instance if x is a point of the fair knapsack polytope defined as follows.

Definition 2.1 (Fair Knapsack Polytope). A feasible fractional solution is a point in the following polytope PFK:

In the previous section, we mentioned that continuous greed can return a fractional solution with a constant approximation. However, the given submodular function f cannot directly evaluate the objective value corresponding to a fractional solution. A common approach in submodular maximization is to utilize the concept of multi-linear extension to assess fractional solutions.

Definition 2.2 (Multilinear Extension). The multilinear extension of a submodular function f is a function F for x = {xe ∈ [0, 1]}e∈E where F(x) is equal to

where D(x) represents a probability distribution over elements, where each element is sampled independently with probability xe, and R is a random subset sampled from this distribution.

It is shown by [Patel et al., 2021] that the problem admits a PTAS when the objective is an additive function (i.e., f(S) = ∑e∈S f({e}) for any S ⊆ E).

Lemma 2.3 ([Patel et al., 2021]). When f is an additive function, there exists an algorithm with running time poly(n, k, 1ϵ ) that returns a solution S such that (i) ∑e∈S f({e}) ≥ (1 - ϵ) · OPTA; (ii) li < |S ∩ Gi| ≤ ui for all i ∈ [k], where OPTA is the optimal solution under the additive function case.

The prior work [Calinescu et al., 2011] introduces a continuous greedy framework to address constrained submodular maximization problems. Their analysis shows that, given any constraints, if the corresponding additive version (i.e., replacing the submodular objective with an additive function) admits a (1 - ϵ)-approximation algorithm, then combining that algorithm with continuous greedy yields a (1-1/e-ϵ)- approximate fractional solution. Therefore, using Lemma 2.3 as a subroutine, it is shown that the continuous greedy algorithm returns a good fractional solution in polynomial time.

Lemma 2.4. Given any instance of FKSM, there is a polynomial time algorithm that returns a point x ∈ PFK such that F (x) ≥ (1 - 1e - ϵ) · OPT for any ϵ > 0, where OPT is the optimal objective value.

3 Knapsack Truncating

In this section, we introduce the knapsack truncating technique and use it to prove the following theorem:

Theorem 1.1. Given an FKSM instance with a constant number of groups, there exists a polynomial-time algorithm that achieves an approximation ratio of 12 (1 - 1e ) - ϵ with probability at least 1- 1e - 1 e2 for any ϵ > 0.

Given an FKSM instance, let S∗ denote an optimal solution for this instance. Since this section focuses on the setting where the number of element groups is constant, through polynomial-time enumeration, we can assume that we know the following for each group Gi:

• The number of elements selected from Gi by S∗ , i.e., the value of γi := |S∗ ∩Gi|.
• The number of elements among the top γi smallestweight elements in Gi that are included in S∗ , i.e., the value of βi := |S∗ ∩ Li(γi)|, where Li(γi) represents the set of the γi smallest-weight elements in Gi (with ties broken arbitrarily).

The reduction method is stated in Algorithm 1. From the description, we observe that during the reduction, both the cost of each element and the knapsack size are reduced. For elements in Li(γi), their costs are set to 0. For each element not in Li(γi), the cost decreases by w(Li(γi))-w(Li(βi)) γi-βi . This reduction amount can be interpreted as the average weight of the γi-βi largest elements in the subset Li(γi). Since Li(γi) is defined as the set of the γi elements in Gi with the smallest weights, we always have each element's new weight in the reduced FKSM instance ¯we ≥ 0.

Algorithmic Intuition. The purpose of knapsack truncating is to transform an FSMK instance into an FKSM instance such that it can be addressed efficiently. A very natural idea is to directly set all fairness lower bounds to zero. Clearly, in this case, the optimality inheritance property (see its definition in Section 1.2 or the lemma below) would always hold. However, the feasibility extension property is unlikely to be satisfied, as it is possible that some weight-heavy elements have already been selected, leaving no room to add more elements to meet the fairness lower bounds.

But we notice that things change if each group contains at least γi elements with a weight of 0. In this scenario, the fairness lower bounds are guaranteed to be met because these zero-weight elements can be selected freely. This suggests that to ensure feasibility extension, we must introduce zero weights into the FKSM instance-some elements' weights need to be reduced to 0. Intuitively, reducing the weights of elements in Li(γi) to zero should have the least impact (as Li(γi) is the set of elements with the smallest weights). Therefore, in our algorithm, we choose to let these elements become zero-weight. Once their weights are set to 0, the knapsack budget should be reduced accordingly by ∑i w(Li(γi)). This adjustment can be seen as reserving space in the knapsack for elements in Li(γi), allowing them to be freely selected later.

However, reducing the budget harms the optimality inheritance property, as the optimal solution may contain many elements outside Li(γi). To ensure that the optimal solution from the original instance still remains feasible under the new budget, we also need to reduce the weights of elements not in Li(γi). Since FKSM and FKSM are not equivalent, we cannot guarantee that all feasible solutions will satisfy the new budget constraint after weight reduction. Nevertheless, based on the characterization of the optimal solution provided by {γi, βi}, we can carefully design the weight reduction strategy to ensure that the optimal solution remains feasible in the new FKSM instance.

Lemma 3.1. Given an FKSM instance I, Algorithm 1 reduces it to an FKSM instance ¯ I (with the same ground elements and objective function) that satisfies the following:

• (3.1a) Optimality Inheritance: The optimal solution S∗ of I remains feasible for ¯ I.
• (3.1b) Feasibility Extension: For any feasible solution ¯ S of ¯ I, there always exists a feasible solution S of I such that f(S) ≥ f( ¯ S)/2.

Proof. We begin by proving the first property. We show that S∗ satisfies both the fairness and budget constraints of the reduced FKSM instance ¯ I.

For the fairness constraints, according to the description in Algorithm 1, each group Gi in the original instance I is split into two groups: Li(γi) and Gi \ Li(γi), with corresponding fairness upper bounds of βi and γi - βi, respectively. Due to the definitions of γi and βi, we directly have |S∗ ∩ Li(γi)| = βi and |S∗ ∩ (Gi \ Li(γi))| = γi - βi. Therefore, S∗ satisfies the fairness constraints of ¯ I.

For the budget constraint, we have

where the last inequality follows from the definition of ¯B, the fact that Li(βi) is the top βi smallest-weight elements in Gi, and that |S∗ ∩Li(γi)| = βi. Thus, S∗ remains feasible for ¯ I. For the second property, given a feasible solution ¯ S for ¯ I, we construct a solution following the procedure described in Algorithm 2. We first prove the feasibility and then analyze its objective value. The algorithm ultimately selects the solution with the larger objective value between S and L(γ). Since L(γ) is clearly feasible, the following focuses on proving the feasibility of S. By the algorithm's construction, S

Algorithm 1 Knapsack Truncating

Input: An FKSM instance characterized by I = (f, {we, δe}e∈E, {li, ui}i∈[k],B) and a corresponding parameter set {γi, βi}i∈[k] .

Output: A reduced FKSM instance.

// Split each group into two groups according to parameter γi, βi in the reduced instance 1: for each group index i ∈ [k] do 2: for each element e ∈ Gi do 3: if e /∈ Li(γi) then 4: Set its new color ¯ δe ← i + k and weight ¯we ← we - w(Li(γi))-w(Li(βi)) γi-βi . 5: else 6: Keep its color ¯ δe ← i unchanged and set its new weight ¯we ← 0. 7: end if 8: end for 9: end for // Construct the upper limit for each new group 10: for each new group index i ∈ [2k] do 11: if i ≤ k then 12: Set ¯ui ← βi. 13: else 14: Set ¯ui ← γi - βi. 15: end if 16: end for // Construct the new budget 17: Set the new budget: ¯B ←B - ∑i∈[k] w(Li(γi)) 18: return ¯ I = (f, { ¯we, ¯ δe}e∈E, {¯ui}i∈[2k], ¯B).

Algorithm 2 Feasibility Extension

Input: A feasible solution ¯ S of the reduced FKSM instance. Output: A feasible solution S of the original FKSM instance.

• 1: for each group index i ∈ [k] do
• 2: Set S ← ¯ S ∩ (Gi \ Li(γi)).
• 3: Add elements fromLi(γi) to S in increasing order of weight until |S ∩Gi| = γi.
• 4: end for
• 5: Let L(γ) := ⋃i∈[k] Li(γi)
• 6: return argmax{f(S), f(L(γ))}.

satisfies the fairness constraints in I, as elements are added to S until |S∩Gi| = γi for each i ∈ [k]. The proof of the budget constraint relies on the fact that elements are added in increasing order of weight (in Line 3 of Algorithm 2). Intuitively, this ensures that the average weight among any subset of these elements is at most w(Li(γi))-w(Li(βi)) γi-βi . For notational simplicity, let κi := | ¯ S ∩ (Gi \ Li(γi))| for each i ∈ [k], and due to Line 3 in Algorithm 2, we have |S ∩Li(γi)| = γi -κi. Thus, the value of w(S) is equal to

where the last inequality uses the fact that, by the algorithm's construction, S∩L(γi) consists of the γi-κi smallest-weight elements in L(γi).

To prove the objective value guarantee, we observe that ¯ S can be partitioned into two parts: ¯ S ∩ L(γ) and ¯ S \ L(γ), which are subsets of L(γ) and S, respectively. Since f is monotone and submodular, we can complete the proof:

Lemma 3.1 demonstrates a desirable reduction from FKSM to FKSM . The last piece in proving Theorem 1.1 is to use an existing algorithm to handle FKSM .

Lemma 3.2 ([Chekuri et al., 2009]). For the FKSM problem, there exists a polynomial time algorithm that returns an approximation ratio of 1 - 1e - ϵ with probability at least 1- 1e - 1 e2 for any ϵ > 0.

Proof of Theorem 1.1. The theorem can be easily proven using the above lemmas. We first reduce the given FKSM instance using Algorithm 1, then apply the algorithm provided in [Chekuri et al., 2009] to the reduced FKSM instance. Finally, we use Algorithm 2 to produce a feasible solution for the original problem. Lemma 3.2 ensures that we can obtain a solution with an approximation ratio of 1 - 1e - ϵ with high probability in the reduced instance, while the two properties from Lemma 3.1 guarantee that the solution constructed by Algorithm 2 will have at most a 1/2 decrease in its approximation ratio, which completes the proof.

4 RandomizedWeighted Pipage Rounding

In this section, we apply randomized weighted pipage rounding to the submodular function case and aim to establish the following theorem.

Theorem 1.2. Given an FKSM instance, if the fairness constraints are relaxed to be satisfied in expectation, there exists a polynomial-time algorithm that returns a solution with an expected approximation ratio of (1 - 1e ) - ϵ for any ϵ > 0.

Algorithm 3 Randomized Weighted Pipage Rounding

Input: An instance with (f, {we, δe}e∈E, {li, ui}i∈[k],B) and a fractional solution x

Output: A rounded solution y.

• 1: Initialize solution y ←x.
• 2: while there are two elements p, q with yp, yq ∈ (0, 1) do
• 3: Let δ1 ←min{yp, (1- yq) · wq wp }.
• 4: Let δ2 ←min{1- yp, yq · wq wp }.
• 5: With probability δ2 δ1+δ2 :

• 6: Otherwise:

• 7: end while
• 8: return y.

The description of the generalized rounding algorithm is provided in Algorithm 3. Note that in the classic pipage rounding [Calinescu et al., 2011] for cardinality constraint, δ1 and δ2 are set to min{yp, (1 - yq)} and min{1 - yp, yq}, respectively. And, the coordinates yp and yq always change at the same rate. However, in the weighted version, we utilize the element weights to guide the rounding process, ensuring that the knapsack constraint is always satisfied. We begin by showing several properties of weighted pipage rounding.

4.1 Rounding Properties

In this subsection, we discuss the properties of weighted pipage rounding from three perspectives: the knapsack constraint (Lemma 4.1), the fairness constraints (Lemma 4.2), and the objective guarantee (Lemma 4.3).

Lemma 4.1 (Knapsack Satisfaction). ∑e∈E weye ≤ B.

Lemma 4.2 (Expected Fairness Satisfaction). For each group Gi, li < E[∑e∈Gi ye] ≤ ui.

Lemma 4.3 (Objective Guarantee). In any iteration, we have E[F (y)] ≥ F (x).

The first two lemmas can be easily proven by performing some mathematical calculations based on the probability distribution defined in Algorithm 3. Due to space limitations, we defer their detailed proofs to [Li et al., 2025].

In the following, we focus on proving the third lemma. During the proof, we build on an existing result (Lemma 4.4) to generalize the convexity of a submodular function's multilinear extension (Lemma 4.5) and then use this convexity property to complete the proof.

Lemma 4.4 ([Calinescu et al., 2011]). Let F : [0, 1]E → R≥0 be the multilinear extension of a set function f : 2E → R≥0.

Lemma 4.5 (Convexity of Multilinear Extension). Let ei denote the vector with a value of 1 in the i-th dimension and 0 in all other dimensions. If f is a monotone submodular function, then its multilinear extension is convex along the line (ciei - cjej) for any i, j ∈ E and constants ci, cj ≥ 0, i.e., the function F a ij (λ) := F(a+ciλei-cjλej) is a convex function for any a ∈ [0, 1]E , i, j ∈ E and constants ci, cj ≥ 0.

Proof. To show the function F a ij (·) is a convex function, it is sufficient to show the second derivative of F a ij is nonnegative. We define the function g(λ) := a + ciλei - cjλej . Note that g(λ) is a set of functions. For each e ∈ E, define ge(λ) as the e-th function of g(λ), i.e., ge(λ) = ae for all e ∈ E \ { i, j }, gi(λ) = ai + ciλ and gj(λ) = aj - cjλ. So, F a ij is a composition function: F a ij = F(g1(λ), . . . , gn(λ)). For simplicity, let ∆ := a+ciλei -cjλej . By the chain rule,

Differentiating one more time and by the chain rule again,

Since ci, cj ≥ 0 and by Lemma 4.4, we get d2F a ij ∂λ2 ≥ 0. Thus, F(a + ciλei - cjλej) is a convex function of λ.

Proof of Lemma 4.3. Let y(t) denote the solution y in iteration t. We prove the lemma inductively by showing that E[F(y(t+1) ) | y(t) ] ≥ F(y(t) ). Assume that y(t+1) and y(t) differ at p, q-th coordinates. Let eq denote the vector with a value of 1 in the q-th dimension and 0 in all other dimensions. By the description of Algorithm 3, y(t+1) becomes y(t) -δ1 · ep +δ1 · wq wp · eq with probability δ2 δ1+δ2 , and y(t) + δ2 · ep - δ2 · wq wp · eq with probability δ1 δ1+δ2 . Define function H(λ) := F (y(t) + λ · ep - wp wq · λ · eq). Then,

4.2 Constant Approximation with Relaxed Fairness

This subsection proves Theorem 1.2. In Lemma 2.4, we demonstrate that the continuous greedy technique can always yield a fractional solution x with an approximation ratio of (1 - 1/e - ϵ). Subsequently, we apply Algorithm 3 to round x into a solution y. Using Lemma 4.1, Lemma 4.2 and Lemma 4.3, we can guarantee that y satisfies the knapsack constraint, (expected) fairness constraints, and maintains the objective value.

However, it is worth noting that the proof does not conclude here. The solution y is not guaranteed to be integral. Due to the different rates at which ye increases or decreases during the rounding process, ∑e ye may no longer be an integer. In fact, y is a nearly integral solution, where "nearly" means that at most one element has a fractional ye ∈ (0, 1), while the remaining components are integers.

Lemma 4.6. The solution y returned by Algorithm 3 is a nearly integral solution. Let z := {ze = ⌊ye⌋}e∈E. We have integral solution z satisfies the knapsack constraint and (expected) fairness constraint.

Proof. It is easy to see that y is a nearly integral solution because if there were at least two fractional components, Algorithm 3 would continue iterating in the while loop. Since ze is the floor of each ye, it follows that ze ≤ ye. By Lemma 4.1, we can verify the satisfaction of the knapsack constraint: ∑e∈E weze ≤ ∑e∈E weye ≤ B.

For the fairness constraints, the continuous greedy process ensures that the ℓ1 norm of the fractional solution within any group is an integer, i.e., ∑e∈Gi xe ≥ li + 1. By Lemma 4.2, the expected ℓ1 norm of y also satisfies E[∑e∈Gi ye] ∈ [li + 1, ui]. Furthermore, since y is nearly integral, the rounding process decreases the ℓ1 norm by less than 1. Hence, for each group Gi, we have:

Proof of Theorem 1.2. Using the above lemmas, we obtain an integer solution z that satisfies the knapsack constraint and the expected fairness constraints. The last step is to analyze the objective value of z. According to the knapsack enumeration technique applied in [Chekuri et al., 2009], we can always ensure, through a polynomial-time enumeration process, that all elements selected via the relax-and-round method contribute only a small constant η to the objective function value. Namely, removing any single element reduces the objective value by at most a factor of (1 + η). Therefore, F(z) differs from F(y) by at most a factor of (1 + η). Furthermore, Lemma 4.3 implies that the expected approximation ratio of z is 1 - 1/e - ϵ.

4.3 Further Discussion

In this subsection, we discuss some additional properties of the randomized weighted pipage rounding, which we believe to be of independent interest. Notably, we observe that the negative correlation and objective concentration properties, previously established in the classic pipage rounding, still hold in the weighted version.

Lemma 4.7 (Negative Correlation). The random variables in { ye }e∈E are negatively correlated, which means that for any S ⊆ E: E [∏e∈S ye ] ≤ ∏e∈S E[ye].

Lemma 4.8 (Objective Concentration). If the objective function f has a marginal value at most 1, for any δ ∈ (0, 1), we have Pr[F (y) ≤ (1 - δ)F (x)] ≤ exp(-δ2 · F (x)/2).

We remark that when generalized to the weighted pipage rounding, many prior properties still hold, but the original proofs are no longer applicable. Since the algorithm now moves the fractional solution along the line ep-eq · wp wq rather than the specific direction ep -eq, all relevant proofs need to be extended. For example, when proving the objective concentration lemma, it is necessary to establish a more general property of the concave pessimistic estimator (see [Li et al., 2025] for details).

5 Conclusion

In this paper, we consider the problem of fair submodular maximization under a knapsack constraint. We introduce two novel techniques: knapsack truncating and randomized weighted pipage rounding, and apply them to derive fair solutions with good approximations. Several directions for future research remain open. For example, when the number of groups is non-constant, it still remains an open question if a non-trivial approximation can be achieved. Investigating whether our proposed techniques can be further extended to this more general setting, or if entirely new techniques are required to resolve this open problem, is an interesting direction for future work.

Acknowledgements

Chenyang Xu is supported by the National Natural Science Foundation of China (No. 62302166), the National Key Research Project of China under Grant No. 2023YFA1009402, and the Key Laboratory of Interdisciplinary Research of Computation and Economics (SUFE), Ministry of Education. We thank the anonymous reviewers for their valuable comments.

Contribution Statement

All authors in the paper have equal contributions and are corresponding authors, and thus, it is ordered alphabetically.