# fair_submodular_maximization_over_a_knapsack_constraint__17b34eed.pdf

Fair Submodular Maximization over a Knapsack Constraint

Lijun Li1 , Chenyang Xu2 , Liuyi Yang2 and Ruilong Zhang3

1 Department of Computer Science, City University of Hong Kong, Hong Kong, China 2 Software Engineering Institute, East China Normal University, Shanghai, China 3 Department of Mathematics, Technical University of Munich, Munich, Germany lijunli3-c@my.cityu.edu.hk, cyxu@sei.ecnu.edu.cn, 10225101401@stu.ecnu.edu.cn, ruilong.zhang@tum.de

We consider fairness in submodular maximization subject to a knapsack constraint, a fundamental problem with various applications in economics, machine learning, and data mining. In the model, we are given a set of ground elements, each associated with a weight and a color, and a monotone submodular function defined over them. The goal is to maximize the submodular function while guaranteeing that the total weight does not exceed a specified budget (the knapsack constraint) and that the number of elements selected for each color falls within a designated range (the fairness constraint). While there exists some recent literature on this topic, the existence of a non-trivial approximation for the problem without relaxing either the knapsack or fairness constraints remains a challenging open question. This paper makes progress in this direction. We demonstrate that when the number of colors is constant, there exists a polynomial-time algorithm that achieves a constant approximation with high probability. Additionally, we show that if either the knapsack or fairness constraint is relaxed only to require expected satisfaction, a tight approximation ratio of (1 1/e ϵ) can be obtained in expectation for any ϵ > 0.

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

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

fairness constraints and the knapsack constraint must be strictly satisfied remains an open problem.

1.1 Problem Definition 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 submodular1 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) := P 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., P e ye = P 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[P e weye] B and the y variables are negatively correlated. Using standard knapsack enumeration tech-

1A 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.

niques [Chekuri et al., 2009], it can be shown that, with high probability (w.h.p.), 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: P 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 FKSM problem, 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.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 1

e ϵ with probability at least 1 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:

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

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 1

e ϵ 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 Related Works 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 1

e)-approximation algorithm [Sviridenko, 2004]. [Kulik et al., 2009] studies submodular maximization subject to a constant number of linear constraints and gives a (1 1 e ϵ) 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 1

e ϵ)-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: (

x [0, 1]E : X

e E wexe B; li < X

e Gi xe ui, i [k]

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

E R D(x)[f(R)] = X

e/ R (1 xe)

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) = P 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) P 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 1

e ϵ) OPT for any ϵ > 0, where OPT is the optimal objective value.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

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 1

e ϵ with probability at least 1 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 P 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

i [k] w(S Li(γi)) + w(S (Gi \ Li(γi)))

i [k] w(S Li(γi)) w(S Li(γi))

+ w(S (Gi \ Li(γi)))

(γi βi) w(Li(γi)) w(Li(βi))

γi βi (Definitions of we, γi and βi)

i [k] w(Li(γi))

i [k] w(Li(βi)) w(S Li(γi))

(Feasibility of S for I)

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

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

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 P 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 from Li(γi) to S in increasing order of weight until |S Gi| = γi. 4: end for 5: Let L(γ) := S i [k] Li(γi) 6: return arg max{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

i [k] w( S (Gi \ Li(γi))) + w(S Li(γi))

i [k] w( S (Gi \ Li(γi))) + w(S Li(γi))

+ κi w(Li(γi)) w(Li(βi))

γi βi B + X

i [k] w(Li(γi)) + w(S Li(γi))

+ κi w(Li(γi)) w(Li(βi))

γi βi (Feasibility of S for I)

i [k] w(Li(γi)) + w(Li(βi))

+ (γi κi βi) w(Li(γi)) w(Li(βi))

+ κi w(Li(γi)) w(Li(βi))

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:

f( S) f( S L(γ)) + f( S \ L(γ)) (Submodularity) f(L(γ)) + f(S) (Monotonicity) 2 max{f(L(γ)), f(S)} .

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

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 1

e ϵ with probability at least 1 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 1

e ϵ 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 Randomized Weighted 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 1

e ϵ 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

4: Let δ2 min{1 yp, yq wq

5: With probability δ2 δ1+δ2 : Set yp yp δ1 and yq yq + δ1 wp

wq . 6: Otherwise: Set yp yp + δ2 and yq yq δ2 wp

wq . 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). P e E weye B.

Lemma 4.2 (Expected Fairness Satisfaction). For each group Gi, li < E[P 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.

x2 i = 0 holds at any point in [0, 1]E for any i E.

(4.4b) If f is submodular, then 2F xi xj 0 holds at any point in [0, 1]E for all i, j E

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,

d F a ij λ =

λ = ci F xi cj F xj

Differentiating one more time and by the chain rule again,

d2F a ij λ2 =

x2 i 2cicj 2F xi xj + c2 j 2F

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 λ.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

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,

E[F(y(t+1)) | y(t)]

= δ2 δ1 + δ2 H( δ1) + δ1 δ1 + δ2 H(δ2)

δ1 + δ2 + δ1 δ2

(Lemma 4.5)

= H(0) = F(y(t)) .

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, P 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: P e E weze P 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., P e Gi xe li + 1. By Lemma 4.2, the expected ℓ1 norm of y also satisfies E[P 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:

e Gi ye 1 < X

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 Q e S ye Q 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.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

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.

References [Ageev and Sviridenko, 2004] Alexander A. Ageev and Maxim Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Comb. Optim., 8(3):307 328, 2004. [Amiridi et al., 2021] Magda Amiridi, Nikos Kargas, and Nicholas D. Sidiropoulos. Information-theoretic feature selection via tensor decomposition and submodularity. IEEE Trans. Signal Process., 69:6195 6205, 2021. [Anegg et al., 2020] Georg Anegg, Haris Angelidakis, Adam Kurpisz, and Rico Zenklusen. A technique for obtaining true approximations for k-center with covering constraints. In IPCO, volume 12125 of Lecture Notes in Computer Science, pages 52 65. Springer, 2020. [Avdiukhin et al., 2019] Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, and Samson Zhou. Adversarially robust submodular maximization under knapsack constraints. In KDD, pages 148 156. ACM, 2019. [Aziz et al., 2024] Haris Aziz, Xinhang Lu, Mashbat Suzuki, Jeremy Vollen, and Toby Walsh. Fair lotteries for participatory budgeting. In AAAI, pages 9469 9476. AAAI Press, 2024. [Backurs et al., 2019] Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scalable fair clustering. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 405 413. PMLR, 2019. [Bao et al., 2022] Wei-Xuan Bao, Jun-Yi Hang, and Min Ling Zhang. Submodular feature selection for partial label learning. In KDD, pages 26 34. ACM, 2022. [Calinescu et al., 2011] Gruia Calinescu, Chandra Chekuri, Martin P al, and Jan Vondr ak. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput., 40(6):1740 1766, 2011. [Celis et al., 2018] L. Elisa Celis, Lingxiao Huang, and Nisheeth K. Vishnoi. Multiwinner voting with fairness constraints. In IJCAI, pages 144 151. ijcai.org, 2018. [Chekuri et al., 2009] Chandra Chekuri, Jan Vondrak, and Rico Zenklusen. Dependent randomized rounding for matroid polytopes and applications, 2009.

[Chekuri et al., 2014] Chandra Chekuri, Jan Vondr ak, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput., 43(6):1831 1879, 2014.

[Chierichetti et al., 2017] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In NIPS, pages 5029 5037, 2017.

[Cornuejols et al., 1977] Gerard Cornuejols, Marshall L Fisher, and George L Nemhauser. Exceptional paper location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management science, 23(8):789 810, 1977.

[Cui et al., 2024] Shuang Cui, Kai Han, Shaojie Tang, Feng Li, and Jun Luo. Fairness in streaming submodular maximization subject to a knapsack constraint. In KDD, pages 514 525. ACM, 2024.

[Dutting et al., 2022] Paul Dutting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, and Morteza Zadimoghaddam. Deletion robust submodular maximization over matroids. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 5671 5693. PMLR, 2022.

[Feldman et al., 2023] Moran Feldman, Christopher Harshaw, and Amin Karbasi. How do you want your greedy: Simultaneous or repeated? J. Mach. Learn. Res., 24:72:1 72:87, 2023.

[Gandhi et al., 2006] Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. J. ACM, 53(3):324 360, 2006.

[Gu et al., 2023] Yu-Ran Gu, Chao Bian, and Chao Qian. Submodular maximization under the intersection of matroid and knapsack constraints. In AAAI, pages 3959 3967. AAAI Press, 2023.

[Haba et al., 2020] Ran Haba, Ehsan Kazemi, Moran Feldman, and Amin Karbasi. Streaming submodular maximization under a k-set system constraint. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 3939 3949. PMLR, 2020.

[Halabi et al., 2020] Marwa El Halabi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakab Tardos, and Jakub Tarnawski. Fairness in streaming submodular maximization: Algorithms and hardness. In Neur IPS, 2020.

[Halabi et al., 2023] Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard, Jakab Tardos, and Jakub Tarnawski. Fairness in streaming submodular maximization over a matroid constraint. In ICML, volume 202 of Proceedings of Machine Learning Research, pages 9150 9171. PMLR, 2023.

[Halabi et al., 2024] Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard, and Thuy-Duong Vuong. Fairness in submodular maximization over a matroid constraint. In AISTATS, volume 238 of Proceedings of Machine Learning Research, pages 1027 1035. PMLR, 2024.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

[Kempe et al., 2003] David Kempe, Jon Kleinberg, and Eva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137 146, 2003. [Krause et al., 2008] Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2), 2008. [Kulik et al., 2009] Ariel Kulik, Hadas Shachnai, and Tami Tamir. Maximizing submodular set functions subject to multiple linear constraints. In SODA, pages 545 554. SIAM, 2009. [Lee et al., 2009] Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Non-monotone submodular maximization under matroid and knapsack constraints. In STOC, pages 323 332. ACM, 2009. [Li et al., 2025] Lijun Li, Chenyang Xu, Liuyi Yang, and Ruilong Zhang. Fair submodular maximization over a knapsack constraint. ar Xiv, abs/2505.12126, 2025. [Lin and Bilmes, 2011] Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Dekang Lin, Yuji Matsumoto, and Rada Mihalcea, editors, Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 510 520, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. [Mirzasoleiman et al., 2016] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submodular maximization: Personalized data summarization. In ICML, volume 48 of JMLR Workshop and Conference Proceedings, pages 1358 1367. JMLR.org, 2016. [Nemhauser and Wolsey, 1978] George L Nemhauser and Laurence A Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3(3):177 188, 1978. [Patel et al., 2021] Deval Patel, Arindam Khan, and Anand Louis. Group fairness for knapsack problems. In AAMAS, pages 1001 1009. ACM, 2021. [Sviridenko, 2004] Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett., 32(1):41 43, 2004. [Wang et al., 2021] Yanhao Wang, Francesco Fabbri, and Michael Mathioudakis. Fair and representative subset selection from data streams. In WWW, pages 1340 1350. ACM / IW3C2, 2021. [Yu et al., 2016] Baosheng Yu, Meng Fang, Dacheng Tao, and Jie Yin. Submodular asymmetric feature selection in cascade object detection. In AAAI, pages 1387 1393. AAAI Press, 2016.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)