Fair Submodular Cover
Authors: Wenjing Chen
Shuo Xing
Samson Zhou
Victoria G. Crawford
Venue: ICLR 2025 Poster (2025)
Keywords: discrete optimization
submodular cover
fairness
Primary area: optimization

Abstract: Machine learning algorithms are becoming increasing prevalent in the modern world, and as a result there has been significant recent study into algorithmic fairness in order to minimize the possibility of unintentional bias or discrimination in these algorithms. Submodular optimization problems also arise in many machine learning applications, including those such as data summarization and clustering where fairness is an important concern. In this paper, we initiate the study of the Fair Submodular Cover Problem (FSC). Given a ground set $U$, a monotone submodular function $f:2^U\to\mathbb{R}_{\ge 0}$, and a threshold $\tau$, the goal of FSC is to find a balanced subset of $U$ with minimum cardinality such that $f(S)\ge\tau$. We first introduce discrete algorithms for FSC that achieve a bicriteria approximation ratio of $(\frac{1}{\varepsilon}, 1-O(\varepsilon))$. We then present a continuous algorithm that achieves a $(\ln\frac{1}{\varepsilon}, 1-O(\varepsilon))$-bicriteria approximation ratio, which matches the best approximation guarantee of submodular cover without a fairness constraint. Finally, we complement our theoretical results with a number of empirical evaluations that demonstrate the efficiency of our algorithms on instances of maximum coverage.

Published as a conference paper at ICLR 2025
FAIR SUBMODULAR COVER
Wenjing Chen"
Shuo Xing"
Samson Zhou
Victoria G. Crawford"
ABSTRACT
Machine learning algorithms are becoming increasing prevalent in the modern world, and as result there has been significant recent study into algorithmic fair- ness in order to minimize the possibility of unintentional bias or discrimination in these algorithms. Submodular optimization problems also arise in many machine learning applications, including those such as data summarization and clustering where fairness is an important concern. In this paper, we initiate the study of the Fair Submodular Cover Problem (FSC). Given a ground set U, a monotone submodular function f 2 - R20, and a threshold т, the goal of FSC is find a balanced subset of U with minimum cardinality such that f(S) 2 т. We first introduce discrete algorithms for FSC that achieve a bicriteria approximation ratio of (g, Os)).. We then present a continuous algorithm that achieves a (In 1, -be))-biciie approximation ratio, which matches the best approxi- mation guarantee of submodular cover without a fairness constraint. Finally, we complement our theoretical results with number of empirical evaluations that demonstrate the efficiency of our algorithms on instances of maximum coverage.
INTRODUCTION
From high-volume applications such online advertising and smart devices to high-impact appli- cations such as credit assessment, medical diagnosis, and self-driving vehicles, machine learning algorithms are increasingly prevalent in technologies and decision-making processes in the modern world. However, the amount of automated decision-makinn has resulted in concerns about the risk of unintentional bias discrimination (Chouldechova 2017 Kleinberg al. [018 Berk al.. (02T). For example, Chierichetti et al. (2017) noted that although machine learning algorithms may not be biased or unfair by design, they may nevertheless acquire and amplify biases already present in the training data available to the algorithms. Consequently, there has recently been significant focus on achieving algorithmic fairness for number of fundamental problems, such as classification (Zafar al., 2017). clustering (Chierichetti et al.) 2017), data summarization (Celis et al.) 201 8b), and matchings (Chierichetti et al. 2019). Though various definitions have been proposed. there is no universal notion of fairness; indeed, determining the correct notion of fairness is an ongoing active line of research. In fact, Kleinberg et al. (2017) showed that three common desiderata of fairness (probabilistic calibration across classes, numerical balance across classes, and statistical parity) are inherently incompatible. Nevertheless, there has been significant focus recently (Chierichetti et al.) 2017 Celis et al., 2018a Chierichetti al. 2019 El Halabi al. 20200] Halabi et al. (024) on the fairness notion that demands a solution to be balanced with respect to sensitive attribute, such as ethnicity or gender.
In this work, we focus on fairness within submodular optimization. Submodular functions infor- mally satisfy a diminishing returns property that exhibited by many objective functions for fun- damental optimization problems in machine learning. In particular, function f : 2" + R is submodular if for every X C Y C and for every x E U Y, we have f(X (x+)
f(X)
f(Y U (x)) f(Y). We further assume f is monotone, i.e., f(Y) 2 f(X) for every X C. Thus, submodular optimization naturally arises in a wide range of applications, such as clustering and facility location (Gomes & Krause 2010 Lindgren et al. 2016), document summarization (Lin Bilmes 201T Wei et al.] 2013;; Sipos et al. 2012), image processing (Iyer Bilmes 2019)
principal component analysis (Khanna et al. 2015). and recommendation systems (Leskovec al. 2007
El-Arini & Guestrin [011] Chen & Crawford 2024b Mítrović et al. 2017 Yu et al. 2018
TTexas A&M University, ij 31975425 977748t wtt.aaaaa.duu... shuoxi ieeoinn@@am.....mm edu, samsonzhou@gma com,
verawford@t.mm.ee

---

Published as a conference paper at ICLR 2025
Avdiukhin et al. 2019 Yaroslavtsev et al. 2020). While submodular maximization has received the most attention, submodular cover is also an important problem arising in machine learning appli- cations (lyer & Bilmes| 2013b; Mirzasoleiman et al. 2013; Soma & Yoshida, 2015; Norouzi-
iet al.] 2016] Mirzasoleiman et al. 2016] Ghuge et al. 2021: Ran et al.) 2022; Chen & Crawford 20244). In monotone submodular cover (SC), the monotone submodular function arises in the con- straint: Given oracle access to a monotone submodular function f 2 + IR and a threshold т, the
goal of SC is to identify a subset S U of minimum cardinality such that f(S) 2 T.
Many applications of submodular functions such as in clustering (Gomes & Krause 2010 Lindgren al.] 2016) and data summarization (Lin & Bilmes 2011 Wei et al., [013] Sipos al. 2012), are also applications where algorithmic fairness is important. Motivated by this, far submodular max- imization (FSM) has been considered under both a cardinality constraint and a fairness constraint (Celis et al.] 201 Sa; Halabi et al., 2020). In the fair setring, we assume that each element in U is associated with a color that denotes a protected attribute, which allows partitioning the ground set U into disjoint groups .i...., UN. Then informally, the goal is maximize the objective while selecting a representative number of elements from each color. Surprisingly, there has been no pre- vious work studying fairess for the submodular cover problem, to the best of our knowledge. Thus in this work, we initiate the study of fairness for monotone submodular cove
Definition 1 (Fair Submodular Cover (FSC)), Given input threshold T, and bounds on the pro- portion of the elements in each group P. and q.- FSC is find argminsgulSt such that Po|S| s |SnU. S S for all e E [N] and [(S) 2 T.
This definition of fairness incorporates multiple other existing notions of fairness, such as diversity rules (Biddle, 2017; Cohoon et al., (013)) statistical parity (Dwork al., 2012), or proportional rep- resentation rules (Monroe| [ 1995; Brill et al, (017). To guarantee the existence of feasible subsets, we assume that the inputs satisfy Ece(M] Pe S I and EeEIN] 9e N To further illustrate FSC, we describe a fair data summarization application. Let U be a dataset that is split into disjoint subsets U1..... Un such that each subset represents some attribute. The function f is a monotone and sub- modular function that measures the information contained in subset X C U. such as a submodular informatin measure (Iyer et al., 2021). The values of Pe and q. for all E [N] and are input by the user. Then FSC asks to find minimum size summary that contains sufficient information (F(S) 2 T), while maintaining balanced representation amongst the attributes (determined by Po. and go).
Our contributions. In this paper, we propose bicriteria approximation algorithms for FSC. An (a, B--brriter approximation algorithm for FSC returns a solution set X that satisfies |X] S O(OPT) Xo| < [X n Uel < X for all E [N]. and f(X) > Br, where OPT is an optimal
solution to the instance of FSC. Notice that the solution of a bicriteria algorithm for FSC always
satisfies the fairness constraint. However, the constraint the function value (f(X) 2 T) might be
violated by a factor of B and therefore the solution is not necessarily feasible. But, if B to close to 1,
we can get a solution that is close to being feasible. We now describe the main contributions of the paper:
In our first result, we take advantage of the dual relationship between FSM and FSC, and present two algorithms that convert bicriteria approximation algorithms for FSM into bicriteria approximation algorithms for FSC in Section 2 The first algorithm, convert-faiz: is designed to convert discrete algorithms for FSM into ones for FSC. In particular, convert- - fair takes a (7, 3)bbicriteriaa approximation algorithms for FSM and converts it into ((1 + 3)3, biccrittrii approximation algorithm for FSC. Our sec-
'Notiee that is not necessarily obvious what values of input т, and Pe: Ye result in an instance of FSC having a feasible solution. In particular, because f is monotone is easy to check whether there exists set X such f(X)= 2 7 by simply testing whether 7 < fU)), but whether there exists such a set that also satisfies the fairness constraint is unclear. We discuss the question of existence of feasible solution further in Appendix
B.4 and throughout the paper assume that values of input and Pe, ge are chosen such that there does exist feasible solution to the instance.
"Notice that this assumption is necessary: If E CNENN Pe > 1, then ECENN| Po|S| > (S). However, by the definition of fairness constraint in FSC, we can get Pel Sc|S| S |S n Ucl- It then follows that Ece(N) Pe|S| & EeeINy [SnU,l = (S], which is a contradiction, implying there are no feasible sets. Similarly, if E.EM Qe 2 we also prove that feasible satisfy the constraint.
2

---

Published as a conference paper at ICLR 2025
ond conversion algorithm, convert-continee takes continuous (7, b-bbbrrrte approximation algorithm and converts it into ((1 + o) 1+3c+ mation algorithm for FSC.
(1-3:)7-2
)-bicriteria approxi-
Using our above result, we are now able to convert existing algorithms for FSM into algorithms for FSC. In particular, the algorithm Fair-Greedy in El Halabi et al. (2020) can be converted into bicriteria (1 + a, 1/2) for FSC. However, a factor of 1/2 on the feasibility constraint of f f(X) 2 T means that our solution is relatively far from being feasible. Motivated by this, our subsequent results focus on developing bicriteria algorithms for FSC that produce solutions arbitrarily close to being feasible. In particular:
In our second result, we develop the first bicriteria approximation algorithms for FSC that find nearly feasible solutions. In particular, propose three bicriteria algorithms for FSM that can be paired with our converting algorithms in order to find approxi- mate solutions for FSC that are arbitrarily close to meeting the constraint f(S) 2 in FSC. The first two algorithms are the discrete algorithms greedy-fat rness-bi and thresho wwwsshooll-ffaa raassnnes-bbl
which both achieve bicriteria approximation ratios of (1- O(e), )), but the latter makes less queries to f compared to the former. The third al- gorithm is continuous one, cont-thresh -tteteeeeeeeeeeyyyyeee -bi, which achieves an improved (1 (e)), In + 1) bicriteria approximation ratio but requires more queries to f. The theoretical analysis of all these algorithms depends on Lemma [ which is one of our cen- tral technical contributions and distinguishes our approach from the traditional submodular cover problem.
By leveraging greeedy- and thresholdd algorithms for convert-fair and sant-thresh-greedy--e we can obtain algorithms for FSC with bicriteria approximation tio of [[1+00) ((1+a) -(E)) and ((1 + a) (Im(2) + 1), 1 - O(s)) respectively. In contrast, using existing algorithms for FSM along with the converting algorithm does not yield solutions that very close to being feasible for FSC. Finally:
as subroutine as a subroutine for
convert-continuon
We perform an experimental comparison between our discrete algorithms for FSC and the standard greedy algorithm (which does not necessarily find a fair solution) on instances of fair maximum coverage in a graph and fair image summarization. We find that our algorithms find fair solutions while the standard greedy algorithm does not, but at a cost of returning solutions higher cardinality.
1.1 RELATED WORK
Celis et al. 201 first gave (1 approxxattiiiio algorithm for fair monotone submodular maximization under a cardinality constraint, which is tight given a known (1 -1/e) hardness of ap- proximation even without fairness constraints (Nemhauser & Wolsey 1978). This is accomplished by converting their instance of FSM into monotone submodular maximization with a specific type of matroid constraint called faimess matroid, which describe in then using existing algorithms for submodular maximization with a matroid constraint. The stan- dard greedy algorithm achieves 1 /22aapproximation ratio for the submodular maximization with matroid constraint (Fisher et al. 1978), and in addition there exists approximation algorithms using the multilinear extension that achieve
detail in Section 1.2 and
1/e approximation guarantee (Calinescu et al. 2007 Badanidiyuru & Vondrák 2014). Halabi et al. (024)) gave a (1 - 1ale--11pppoonnii -pparxpxxxiiiiiion algorithm for fair monotone submodular maximization under general matroid constraints, though their algorithm only achieves the fairness constraints in expectation. Fair submodular optimization has also been under both cardinality and matroid constraints in the streaming setting (El Halabi et al.) 2020 Halabi
ct al. 2024).
For the classical submodular cover problem without fairness constraints and integral valued f. the standard greedy algorithm, where the element of maximum marginal gain is selected one-by-one un- til f has reached т, has been shown to have an approximation ratio of O max.eu f()) [Wolsey]
1982.. To deal with real-valued f (as in our case), slight variant of the greedy where we stop at E)T instead of r has been shown to be a (n()))), e)- bibcriittriaa approximation algorithm Krause al. 2008). On the other hand, set cover is special case of fair submodular cover (FSC),
3

---

Published as a conference paper at ICLR 2025
and by the result of Feige 1998), it is not possible achieve (1 (1-o(1)) In(n) approximation to FSC unless NP has "slightly superpolynomial time algorithms"". Therefore, a large part of our motivation in considering bicriteria approximation guarantees for FSC is to develop constant factor approximation at the price of a small reduction to feasibility. Indeed, for a fixed e, our algorithms achieve constant factor approximation. If set 1/n, our continuous algorithm (Algorithm 2) for FSM with the converting algorithm (A (Algorithm 4) achieves a ((1 + a) In(n) + 1), 1 - 7/n) bicriteria approximation guarantee for an instance of FSC, and so is very close to being feasible while having an approximation guarantee close to the lower bound.
Although submodular maximization has received relatively more attention than submodular cover, the problems have a dual relationship and thus, natural approach for submodular cover is to con- vert existing algorithms for submodular maximization into ones for cover <lyer Bilmes, 2013a Chen & Crawford 2024a). In particular, Iyer & Bilmes 2013ab showed that given (7, -))--rrritteria approximation algorithm for submodular maximization with a cardinality constraint, one can pro- duce a (1++a) -iibiiiitei approximation algorithm for submodular cover by making log1+a(() (n) guesses for [OPT] in the instance of submodular cover, running the submodular maximization al- gorithm with the cardinality constraint set to each guess, and returning the smallest solution with f value above yr. However, this approach does not take into account the faireess constraints and cannot be used convert algorithms for FSM into ones for FSC.
1.2 PRELIMINARIES
We now present preliminary definitions and notation that will be used throughout the paper. OPT refers to the optimal solution of a submodular optimization problem. We use [A] to denote the set {1. ..., Nj. The marginal gain of adding an element to the subset S is denoted addition, for any vector 전 = (01, 12 V2...., UN). and any k E R, we define kū = (Iu,, kVz, .... kuN) ) and we define [0] (f0, [ ..., [uN]] and [J] = (Lu, [12], [vN]).
Af(S,s) s). In
We now define the related problem of fair submodular maximization (FSM) of a monotone sub- modular function f (EI Halabi et al. 2020), as the search problem of max (f(() :S C U,le s [S n Uel I Ue, Vc E [|] S k where le and ue are the bound of cardinality within each small group. Without loss of generality, in this problem,
assumed that Ece(N] Ue 2 k. This is be- cause Ece[N] "e < k. then |S| = Eee[N] [ ECE[N] We S k. Therefore, the problem equivalent to setting k = E>e[N]
Since for the cover problem, the objective is to minimize the cardinality of the solution set which means |S| is not fixed as it is in FSM, therefore we introduced the definition of fairness for FSC as a natural modification of the above problem where the fairness constraint is proportion of the solution size as opposed to fixed value.
The set of subsets satisfying fairness constraint above for FSM is not a matroid. However, was proven by Halabi et al. (2020) that we can convert instance of FSM into instance of submod- ular maximization problem with a matroid constraint; we state this result as Lemma 3 in Appendix
A This matroid constraint is called a fairness matroid, which we denote as M Mfair K, [, = IS SUCU |S S Me, Yc E [N]. EeE(N max(1S n Uc] S k), where P = (UI,.., UN) is the partition of the ground set U. the total cardinality constraint, ,, E NN are the lower and upper bound vectors respectively. Below we propose the idea of a 3-extension of a faimess matroid, which we will use in our bicriteria algorithms for FSM.
Definition 2. For any B E N+, we define the B-extension of the fairness matroid to be MM = Mfair Bx, BT, Bū) {S C U. S Bu,, Vc E [N], EceME max[[SnU.l. 3le) I 3x).
Our continuous algorithms will use the multilinear extension of f. defined as follows.
Definition 3. For any submodular objective f + R4 with |U] n. the multi-linear extension of f is defined as F(x) = Esço TLE 3; Tles(( - 21)) where x [0, 1]", and xa is the i-th coordinate of x. If we define S(x) to be a random set that contains each element i E with probability I. then by definition, we have that F(x) (S()x))
We now present the definitions of discrete and continuous algorithms with an (a,, 8))-bcritteria ap- proximation ratio for FSM, which is defined to find arg max max.eeM (ar [SS).
4

---

Published as a conference paper at ICLR 2025
Definition 4. A discrete algorithm for FSM with an (a, (o,,B)-bicrnn -bbbritttiiiiia approximation ratio returns
solution X such that
[(X) 2 (((PPT)
VC [ [XUU S Bues
max n NUll, S 3k.
CE[N]
Here OPT is the optimal solution of the problem FSM, i.e., OPT arg max je (S)..
By this definition, we have that an algorithm satisfies (a, 3--brritta approximation ratio for FSM if.. the output set S satisfies f(S) 2 af(OPT) and that S E Ma.
Definition 5. continuous algorithm with (a, B)-bicritteria approximation ratio for FSM returns fractional solution x such that
F(x) 2 a(((P))
x X P(Ma).
Here OPT is the optimal solution of the problem FSM, i.e., OPT = arg max ma (Pa. f(S).
Ma is the B-extension of the fairness matroid M fair ( (P, ā, it), and P(Ms) is the matroid poly- tope of Ms. More specifically, ((M2) = cone E &Ma}.
2 CONVERSION ALGORITTMS FOR FSC
In this section, we introduce two algorithms that make use of the dual relationship between FSC and FSM, and convert bicriteria approximation algorithms for FSM into ones for FSC. The first algorithm, convert-fair, is designed to convert discrete algorithms for FSM into ones for FSC. In particular, convert ffaverrttiirrr takes an (7, 3))bbrrittriiaa approximation algorithms for FSM that runs in time (nn, k) and converts it into a a))+ 7)-bicriteria approximation algorithm for FSC that runs in time O( log([OPT])> [o [nn, (1 + a))OP))) However, because of the matroid constraint, better approximation guarantees for FSM may be achieved by a continuous algorithm that produce fractional solution. Motivated by this, our second converting algorithm, convert-cont nuous, takes a continuous (7, -bbbciiita approximation algorithm (where guarantees are with respect to the multilinear extension as described in Section 1.2). and converts it into a ((1+a) (1-3e)1-24) 1+3++
bicriteria approximation algorithm for FSC. In the next section, we will develop corresponding bicriteria approximation algorithms for FSM that can be used along with the results in this section in order to produce approximately optimal solutions for FSC that are arbitrarily close to being feasible.
For both algorithms, it is required that the sets Ug for E [N] be sufficiently large that method of constructing solution does not run out of elements to pick. In particular, we assume that
the instance of FSC satisfies that Σ Eee(N) min (yer {[I+a)]OPTT) > 1. Recall from the definition
[U_]
of FSC that it is already assumed EcE[N] 9c 1, so this assumption is essentially requiring that there enough elements within each set U, of the partition, relative to parameters a and 33 to ensure that the rank of the B-extension of the fairesss matroid MMg (see definition in Section I.2) is 3K. For example, with the existing algorithm for FSM in El Halabi et al. (2020). is and therefore the assumption is met if [U.] 2 9.(1 + OPT for all [N. For algorithms mentt-thres--geeeee
greedy-fa rness-br and In(e/e) respectively, and the assumption is met if [Ual qe + a) and U. 2 9o(1 + a) OP(T for all E [N] respectively.
in Section 3 B would be 1/c and
We first consider our algorithm convert-fais for converting discrete algorithms for FSM. Pseu- docode for convert-fais is provided in Algorithm | convert- fairr takes as input an in- stance of FSC, a (y. biibriiite approximation algorithm for FSM, and a parameter a > Each iteration of the while loop from Line 2 to Line g corresponds to a guess к on the size of the op- timal solution to the instance of FSC. For each guess K, we have an instance of FSM with budget k, fairness vector of lower bound sp, fairness vector of upper bound kq.. We then run the algo- rithm for FSM on this instance to get set S. Notice that this algorithm will convert the matroid corresponding to the instance of FSM into its 3-extension. In Lines 6 to 8 convert fair adds additional elements so that the lower bounds are met for every one of the partitions. Next in Lines 10 to 12 convert-fair then adds elements until the size constraint 3K is met, without breaking the fairesss constraints. Finally, convert- -artt--falh fairr checks the set S satisfies fS) 2 YT. If it does not, the guess of optimal solution size increases by factor of + a and the process repeats itself.
5

---

Published as a conference paper at ICLR 2025
Algorithm convert-fail
Input: An FSC instance with threshold 7, fairness parameters p. q, partition of U P, (1, 9) bicriteria approximation algorithm for FSM, 0
Output: S
1: A < (1+ at) O.
2: while f(S) < YT do
3: S + Run (7, appppoxxiinnnon algorithm for FSM with fairness matroid
Mjair (P, K. [g<],[9<|)
4:
K6 f- [(1 + a)
5:
//Rounding the solution
6:
for E [N] do
7:
[S n < [ then
8:
Add new elements from U./S $ S until U. 2 3[pon]
9:
if S < B1 then
10:
for e E [N] do
11:
while S < BK and |S Un| < [g do Add new elements in U./S to
12:
return S
We now state the theoretical results for convert ffir below in Theorem We defer the proof and analysis of the proof of Theorem to Appendix C.I
Theorem 1. Suppose EeeNy min 8[1+]] 2 1. Then any (r, B) biccriria approxi- mation algorithm for FSM that returns solution set in time T(n,x) k) can be converted into an approximation algorithm for FSC that is ((1 + a33,7) --bicririii approximation algorithu that in time O log( (PT)) T(n, (1 + a)PPT)).
log(a+1)
We now present our algorithm convert-conte iotaninnuou inuous for converting continuous algorithms. To motivate it, notice that here we can't directly use the converting theorem for discrete algorithms. There are two reasons for this: (i) The output solution is fractional (ii) the bicriteria approximation ratio for the continuous algorithms is on the value the multi-linear extension and don't have exact access F, Line convert- fair. Then we develop the converting algorithm convert - -oontiotinnnoo inuous for continuous algorithms. The key idea of the converting theorem is similar convert fair, so we defer the pseudocode of convert-cont inuous to Algorithm $ in Section C.2 of the appendix. Here we describe the major differences. For each guess of optimal solution size re, Convert-conte contt-cootiuuuss invokes the continuous subroutine algorithm for FSM to obtain frac- tional solution x. Since F can't be queried exactly in general, we estimate F(x) by taking a sufficient number of samples in Line Once the estimate of F(x) is higher than yT, we use the pipage round- ing technique to convert x into a subset S, and then use the rounding procedure analogous to that in Lines 6 to 12 in Algorithm to to obtain a solution set with fairness guarantee. Notice that since the solution set obtained from the pipage rounding step is only guaranteed to satisfy that (f) 2 Fxx), the function value in Theorem 5 holds in expectation. The corre- sponding theoretical guarantees for convert -cont inuous are stated below in Theorem 2 The proof of Theorem 2 can be found in Section C.2 of the appendix.
need rounding step, and
can't check directly if F(x) 2 7r
did on
the approximation guarantee
Theorem 2. Suppose ECE(N) min (ge, 3[1+a) (PPT) }
Then with probability at least 1 8, any (y, bicbriria approximation algorithu for FSM that returns a solution set in time T(n, x) with probability at least 1 & can be converted into an approximation algorithm for FSC that is
W.
((1+a)3, (1-35)n-25 25 bbicriteriaa approximation algorithm where (1-3ely-22 28 holds in expectation. 1+3e+
1+3e+
[ug(lOPT) ((1, (1 ++)OPTP) + log14. [OPT] log[a+1)
The query complexity is at most O
log 12

---

where we assume ECEIN] min(ger ([+o)JOPTT) 2 1 in both Theorem and Theorem we have Published as a conference paper at ICLR 2025
3 BICRITERIA ALGORIHTMM FOR FSM
In the last section, we propose converting algorithms to convert bicriteria algorithms for FSM into ones for FSC. Existing algorithms for FSM can be used as the input (7, (7,,))bicrittrii subroutine, but these algorithms all return feasible solutions to the instance of FSM and have guarantees of / and y S 1 1/e. After applying the converting algorithms in Section 2 this results in solutions for FSC that are far from feasible. For example, the greedy algorithm for FSM proposed has 7 1/2
and [ = 1, and the continuous greedy algorithm for FSM has 7 = 1/e and 3 = (Celis et al,, 201 Sap.
In this section, we propose new algorithms that can be used for FSM where y is arbitrarily close to I and 3 > 1. As a result, the algorithms proposed in this section can be paired with the converting theorems in Section 2 to find solutions to our instance of FSC that are arbitrarily close to being feasible. We propose three bicriteria algorithms for FSM. The first two algorithms are the discrete algorithms greedy-fairnese fnnssairneesbbii and fhzeeholddfaiineee criteria approximation ratios of (e)), 2) where the former is in time (nx//) and the latter in time ( log ) The third algorithm is a continuous one, mentttthres--greedd achieves a (1 (e)), In + 1) bicriteria approximation ratio in time O ( {2* (n²(n)))
which both achieve bi-
which
In the case of submodular maximization with a cardinality constraint without fairness, one can find off of that of the optimal solution by greedily
solution with f value that is factor of adding (In(L/E)) elements beyond the cardinality constraint k. However, existing algorithms for FSM transform the instance into an instance of submodular maximization subject to fairness matroid constraint, and it is not clear how one can take an analogous approach and produce an infeasible solution in order to get better approximation guarantee when dealing with matroid constraint while maintaining a fair solution. We propose the 3-extension of a fairness matroid, defined in Section 1.2 in order to get a (7, bibbriitiet algorithm for FSM with y > 1/c. In particular, we will return solution that is a feasible solution to the 3-extension of the fairness matroid corresponding to our instance of FSM.
We now introduce two lemmas concerning the 8-extension of a matroid that will be needed for our algorithms and their theoretical analysis. Before we proceed to present our algorithms, we first introduce the following general lemma that helps to build a connection between the fairness matroid M and its --extension Mg. For the sake of simplicity in notation throughout this section and
its subsequent proofs, we use the notation M3. representing the 8-extension of MMair k. IT,,, which is defined in Section 1.2, Since the bicriteria algorithm for FSM is designed as a subroutine for the converting theorem with input M M (P, pk. qr), we have that here l. = [Pot]] and u, = [9om]] From the fact that EnEiN Pe S 1 S Lee(N) qo, we have that >>E(N| le S K S E<e(N) Ue-
Since the bicriteria algorithm for FSM is used as a subroutine for the converting theorems for FSC, [U,]
that rank(M fair (P,,, 7)) = and that rank(Mp) BB.. Therefore, we have the following Lemma D
Lemma 1. ECEIN 4 S EcENN Ue and rank aank(Mjair (P, = K. rank(Ms) = 3x.
Next, we present Lemma 2 which is one of the most interesting and novel parts of our analysis in proposing the bicriteria algorithm for FSM, and is necessary in the proof of all the bicriteria algo- rithm for FSM. Notice that in the bicriteria algorithm for submodular maximization with cardinality constraint, the greedy step is achieved by simply adding the element with the highest marginal gain. However, since we need to consider the fairess constraint in our paper, we can only add the ele- ment that makes the solution set feasible. To prove the theoretical guarantee, we have to construct a mapping from the solution set to the optimal solution. To tackle this difficulty, we propose and analyze Lemma 2, which guarantees the existence of such a mapping.
Lemma 2. For any B E M4 and any fairness matroid M fair P.N.T, T, ū). denote M, as the B-- extended fairness matroid of Mfsr (P,K, [, Then for any set S E Mg with |S] = Br. T M Mfair (P, K. i)) with [T'] K, and any permutation of S = (s), ..., sex), there exist a sequence E (E1, E2, m. eBx) such that each element in T appears B times E and that
S U (c++1) E MM,
Vi E (0, 1,...,B.,, Bx}
7

---

Published as a conference paper at ICLR 2025
where St ($1, $2...., 8:) and So O.
Notice that this mapping is not straightforward and trivial due to two reasons. First of all, the size of the optimal solution and the solution set are different. Second, the portion of |S n Ue over [T nua can be different for different subroup c [N]. To prove Lemma 2 we construct the mapping by an iterative proof and by dealing with different cases for each step. This lemma is of great importance
in our analysis it guarantees the existence of a mapping from the solution set to the set containing 3 copies of the OPT. The detailed proof of this lemma is deferred to the appendix.
On the other hand, highlight that this lemma reveals important and general fact about the fairness matroid: For each base set T E MM (P, K. I, ti), and each subset S E MMs that is a base set, we can find a mapping from I" to a sequence E that contains 8 copies of I such that S, U {e: always feasible for Mg. Notice that since Mg is a matroid, then for any subset Si S S2, if S2 E .Ms then S MM.. Consequently, the above lemma holds for not only just base set of Ms, but also for any subset of M, by adding dummy variables to the end the sequence the number of elements in S is less than BK. Building upon this lemma, we propose three bicriteria algorithms in the following part.
3.1 DISCRETE BICRITERIA ALGORITHMS FOR FSM
We now analyze two discrete bicriteria algorithms for FSM, greedy-fair-bl and thresholds d-olddfffi rness-bi. Let SMMC refer the problem of monotone submodular max- imization with matroid constraint. which is well-known to produce a feasible solution with 1/2 approximation guarantee in ((n)) time for SMMC (Fisher et al. 1978), where k is the rank of the matroid. greedy-fal r-bi proceeds in a series of rounds, where at each round we select the element x E with the high- est marginal gain to f that stays on the 1/e-extension of the faimess matroid corresponding to the instance of FSM, i.e. SU (r) E Maje- thresho lochoodd-aa d fai rness--es----- bi based on the thresh- old greedy algorithm (Badanidiyuru
peredy-fair-ie
is based on the standard greedy algorithm
Vondrák 2014). which is also a 1/2 E approximation for rness bi iteratively makes passes through the universe U and adds all elements into its solution with marginal gains exceeding that are feasible with respect to the 1/s-extension of the faimess matroid, and this threshold is decreased by 1-6 e at each round until falls below stopping criterion. Notice that these algo- rithms specifically use the B-extension of the fairness matroid, and therefore do not apply to the more general setting of submodular maximization with a matroid constraint. Pseudocode for the algorithms greedy-fair-bs and Shreshold-fairnes bbi are included in Appendix D as Algorithms
SMMC but requires only On log k) queries of f. Phrreshol--foe
5 and rreppeciveell
and The key benefit these algorithms over existing ones for FSM is that by making arbitrarily small and using convert- convert-faire in Section [ we have algorithms for FSC that are arbitrarily close to being feasible. In particular, if we use pepeedy-fair-ae as subroutine in convert-fair, we have ( +111 E)-bicriteria algorithms for FSC in ((nloo)))x/=²) queries of f. If we use threshold-fate approximation guarantee in On log(n) log(k/<))c²) queries of f. The proofs of both of these theorems can be found in Section Df the appendix.
We now present the theoretical guarantees of greedy-fai
-bi, we get similar
Theorem 3. Suppose that greedy-fat rness-bi is run for an instance of FSM, then greedy-fai fwi.sssrbrsbbbii outputs a solution S that satisfies a (1 - bicritri approximation guarantee at most O (nx/a) queries s.
is run for an instance of FSM with outputs a solution that satisfies a (1 2e, ))- bicriteria approximation guarantee in most O (n/e log(s/s)) queries of f.
Theorem 4. Suppose that threshold-fairnesse
E E (0. Then threshold-fairnesse
3.2 CONTINUOUS ALGORITHMS FOR FSM
A downside to the discrete greedy algorithms proposed in SectionBlis that we are above budget by a factor of 1/E, which is weaker than the analogous guarantee of (1(/=)) that the greedy algorithm gives for submodular maximization with cardinality constraint without fairness. We now introduce
8

---

Published as a conference paper at ICLR 2025
Algorithm 2 cont wownt-tttessggeeeeeeeeee (cont (cont-Ba
Input: E, 6, M 2"
2: x << 0
3: := max f(s),
4: fo 1/2 do
5:
B -t-eereaainngttrrehhodd-ppoooooo
(x, d,
6: x
7: return
Algorithm 3 - (DTP)
1: Input: x, e, 6, d, M 2
2: B
3: Denote MMaar (Pa (
as Min(1s)-
4: for d; w ed. w(1 -) do
5: for u E do
6:
X Af(S(x+ el))
7:
if B {u) E Min(//5)+1 then
8:
X t average over log An
e ş samples from Xx
9:
if X > then B (u
11: W w(1 =)
12:
return B
and analyze our continuous algorithm cont cont-threshe seattttteehggreed-bbbbe (cont-bl) bi), which produces fractional solution for FSM that achieves (1 - (1)0(e), In)),nn(1//) In((/e) 1)-birittrra approximation ratio the continuous threshold greedy algorithm of Badani- diyuru & Vondrák (2014). Compared to the discrete algorithms presented in Section 3.1 cont-bi improves the ratio on the cardinality of the solution from ((1/e) to (1l(11/e) and therefore has as strong of guarantees as the greedy algorithm without fairness. We can achieve a discrete solution with an arbitrarily small loss by employing rounding schemes, like swap rounding (Chekuri et al.)
in O (nx In (n)) time. cont-bi is based
2010), on the returned fractional solution
cont-bi iteratively takes a step size e in direction 1B, where 1 the indicator func- tion of a set B C U. over 1/2 iterations. At each step, the set B is determined by the subroutine (DTP). DTP builds B over a series of rounds corre- sponding thresholds w, where w begins as the max singleton marginal gain and the rounds exit once w sufficiently small. During each round, we iterate over the universe U, and if an ele- ment U can be added B while staying the In(1/e) + 1-extension of the fairness ma- troid, then we approximate the multilinear extension f and add u to B if and only if the marginal gain above w. Pseudocode for cont-bi is provided in Algorithm is provided in Algorithm
and pseudocode for
Theorem 5. Suppose that Algorithm 2 run for an instance of FSM, then with probability at least n2. cont cont-thresh-greede bi outputs a solution S that satisfies (1 - 7e, In)) + 1)-
bicriteria approximation guarantee in most O nus In (n/e)) queries of f-
By applying a converting theorem, we can obtain the algorithm for submodular cover that achieves an approximation ratio of ((L ([L+a) (In 1). 1()),, which aligns with the best-known results for bicriteria submodular cover without the fairness constraint (Chen & Crawford] [024a Iyer & Bilmes 2013b). The detailed theoretical guarantee and proof of the algorithm can be found in Corollary 5.1 in the appendix.
4 EXPERIMENTS
In this section, we evaluate several of our algorithms for FSC on instances of fair maximum cover- age, where the objective is to identify set of fixed nodes that optimally maximize coverage within

---

Published as a conference paper at ICLR 2025
D
0,20
...00
0.15
0:15
0.4
DE
ZH
DE
ZH
0.10
DE
0.2
0.05
0.05
RU
FR
RU
FR
RU
FR
greedy-bl
(b) greody-falrness-l
(c) thrreshold-fal
2.0 x10*
GREEDY THRES-Fair
difference
300
Value off
GREEDY THRES-Fair
1.2
Cost
200
0.4
GREEDY
0.8
100
THRES-Fair
0.4
1500
1500
0.0
1500
2500 Value of the given threshold
Value of the given threshold
Value the given threshold
(d) f
(c) Cost
(f) Fairness difference
Figure 1: Performance comparison the Twitch_500k dataset for Maximum Coverage. la 1b lc
illustrate the distribution of users speaking different languages in the solutions produced by various algorithms with 2400. f: the value of the objective submodular function. Cost: the size of the returned solution. Fairness difference: (max. |S Ucl min. |S Uc))/SS).
a graph. The dataset utilized is a subset of the Twitch Gamers dataset (Rozemberczki & Sarkar 2021), comprising 5,000 vertices (users) who speak English, German, French, Spanish, Russian, or Chinese. We aim to develop a solution with a high value exceeding given threshold т while ensuring fair balance between users who speak different languages. Additional discussion about the application well experimental setup including parameter settings are included in Appendix addition, we include experiments on instances fair image summarization Appendix G
We evaluate the performance of our discrete bicriteria algorithms greedy-fair-be and sosshodd-fairesse
for FSM as subroutines our algorithm convert- In ad- dition, consider the baseline algorithm, greedy-bll bbi, which is the standard greedy algorithm for submodular cover without fairness. Figures Ta 1b and Jcshowase the distribution of users speaking different languages in the solutions produced by these algorithms with 2400. Figures [d] Te and If present the performance of these algorithms (f value, cost, and fairness difference) for varying values of As shown in Figure la with 2400, over 80% of the users in the solution returned by greedy-bi. are English speakers, which indicates lack of fairness in user language distribution. While the solutions produced by greedy ffrir-biiii and threshold-fate www.lddfffiiiss---ee significantly fairer distributions across diffferent languages, demonstrating the effectiveness of our proposed algorithms. Further, as the value of given T increases, the magnitude of this difference also increases (see Figure (T). Figure Id showcases that for all these algorithms the objective function value f(S) scales almost linearly with the threshold т. which aligns with the theoretical guarantees of the approximation ratio. Additionally, our proposed algorithms is higher than that of the solution from greedy-bi. This is an expected trade-off, algorithms have to include more elements to maintain the approximation ratio while ensuring faimess. Overall, our proposed algorithms are efficient and effective in producing a fair solution.
exhibit
shown in Figure Te| the cost of the solutions returned by
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
Samson Zhou is supported in part by NSF CCF-2335411. The work was conducted in part while Samson Zhou was visiting the Simons Institute for the Theory of Computing as part of the Sub- linear Algorithms program. Victoria Crawford is supported in part by the Seed Program for Al, Computing, and Data Science created by the Texas A&M Institute for Data Science.
REFERENCES
Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavisev, and Samson Zhou. Adversarially robust submodular maximization under knapsack constraints. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD., pp. 148-156, 2019.
Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular func- tions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 1497-1514. SIAM, 2014.
Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, 50(1):3-44 3444, 2021.
Dan Biddle. Adverse impact and test validation: A practitioner's guide to valid and defensible employment testing. Routledge, 2017.
Markus Brill, François Laslier, and Piotr Skowron. Multiwinner approval rules as apportion- ment methods. In Proceedings of the Thirty-Fitt First- AAAI Conference on Artificial Intelligence, pp- 414-420, 2017.
Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing submodular set function subject to a matroid constraint. International Conference on Integer Programming and Combinatorial Optimization, pp. 182-196. Springer, 2007.
L. Elisa Celis, Lingxiao Huang, and Nisheeth K. Vishnoi. Multiwinner voting with fairness straints. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intel- ligence, IJCAI, pp. 144-151, 2018a.
L. Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, and Nisheeth K. Vishnoi. Fair and diverse dpp-based data summarization. In Proceedings of the 35th International Conference on Machine Learning, ICML, pp. 715-724, 2018b.
L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with fairness constraints. In 45th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 28:1-28:15. 2018c.
Chandra Chekuri. Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 575-584. IEEE, 2010.
Wenjing Chen and Victoria Crawford. Bicriteria approximation algorithms for the submodular cover problem. Advances in Neural Information Processing Systems, 36, 2024a.
Wenjing Chen and Victoria G Crawford. Linear submodular maximization with bandit feedback. arXiv preprint arXiv:2407.02600 2024b.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pp. 5029-5037, 2017.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Matroids, matchings, and fairness. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS, 2019.
11

---

Published as a conference paper at ICLR 2025
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
Joanne McGrath Cohoon, James P. Cohoon, Seth Reichelson, and Selwyn Lawrence. Effective recruiting for diversity. In IEEE Frontiers Education Conference, FIE, pp. 1123-1124, 2013.
Pinar Duygulu, Kobus Barnard, Joao FG de Freitas, and David A Forsyth. Object recognition as machine translation: Learning lexicon for a fixed image vocabulary. In Computer Vision-ECCV 2002: 7th European Conference on Computer Vision Copenhagen, Denmark, May 28-31 31, 2002 Proceedings, Part IV 7, pp. 97-112. Springer, 2002.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science, pp. 214-226, 2012.
Khalid El-Arini and Carlos Guestrin. Beyond keyword search: discovering relevant scientific litera- ture. In Proceedings of the 17th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 4339-477 ACM, 2011.
Marwa El Halabi, Slobodan Mitrovié, Ashkan Norouzi-Fasd Fardd Jakab Tardos, and Jakub M Tarnawski. Fairness streaming submodular maximization: Algorithms and hardness. Advances in Neural Information Processing Systems, 11113390-16222 2020.
Uriel Feige. A threshold of In for approximating set cover. J. ACM, 45(4):634-652, 1998.
Marshall L Fisher, George L Nemhauser, and Laurence A Wolsey, An analysis of approximations for maximizing submodular set functions-11. Springer, 1978.
Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. GPTQ: accurate post-training quantization for generative pre-trained transformers. CoRR, abs/2210.17322, 2022.
Rohan Ghuge, Anupam Gupta, and Viswanath Nagarajan. The power of adaptivity for stochastic submodular cover. In International Conference on Machine Learning, pp. 3702-3712. PMLR, 2021.
Ryan Gomes and Andreas Krause. Budgeted nonparametric learning from data streams. In Pro- ceedings of the 27th International Conference on Machine Learning, ICML, pp. 391-398, 2010.
Marwa El Halabi, Slobodan Mitrovic, Ashkan Norouzi-Fart Fard, Jakab Tardos, and Jakub Tarnawski. Fairness in streaming submodular maximization: Algorithms and hardness. In Advances in Neu- ral Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020.
Marwa El Halabi, Suraj Srinivas, and Simon Lacoste-Julien. Data-efficient structured pruning via submodular optimization. Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurIPS, 2022.
Marwa El Halabi, Jakub Tarnawski, Ashkan Norouzi-Fard, and Thuy-Duong Vuong. Faimess in submodular maximization over a matroid constraint. In International Conference on Artificial Intelligence and Statistics, pp. 1027-1035, 2024.
Rishabh Iyer and Jeffrey Bilmes. Near optimal algorithms for hard submodular programs with discounted cooperative costs. In Proceedings of Machine Learning Research, volume 89, pp. 276-285, 2019.
Rishabh Iyer. Ninad Khargonkar, Jeff Bilmes, and Himanshu Asnani. Generalized submodular in- formation measures: Theoretical properties, examples, optimization algorithms, and applications. IEEE Transactions on Information Theory, 68(2):552-781, 2021.
Rishabh K. Iyer and Jeff A. Bilmes. Submodular optimization with submodular cover and submodu- lar knapsack constraints. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems, pp. 2436-2444, 2013a.
Rishabh K Iyer and Jeff A Bilmes. Submodular optimization with submodular cover and submodular knapsack constraints. Advances in neural information processing systems, 26, 2013b.
12

---

Published as a conference paper at ICLR 2025
David Kempe, Jon M. Kleinberg, and Eva Tardos. Maximizing the spread of influence through social network. Theory Comput., 1 11:105-147, 2015.
Rajiv Khanna, Joydeep Ghosh, Russell Poldrack, and Oluwasanmi Koyejo. Sparse Submodular Probabilistic PCA. In Proceedings of the Eighteenth International Conference on Artificial Intel- ligence and Statistics, pp. 453-461, 2015.
Jon Kleinberg, Himabindu Lakkaraju, Jure Leskovec, Jens Ludwig, and Sendhil Mullainathan. Hu- man decisions and machine predictions. The quarterly journal of economics, 133(():237-293, 2018.
Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. 8th Innovations in Theoretical Computer Science Conference, ITCS, pp. 43:1 13:223, 2017.
Andreas Krause, H Brendan McMahan, Carlos Guestrin, and Anupam Gupta. Robust submodular observation selection. Journal of Machine Learning Research, 9(12), 2008
Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Na- talie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 42.-220449 ACM, 2007.
Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Pro- ceedings of the 49th Anmual Meeting of the Association for Computational Linguistics: Human Language Technologies- vovllui 1, pppppp..0 510-520. Association for Computational Linguisties, 2011.
Erik M. Lindgren, Shanshan Wu, and Alexandros G. Dimakis. Leveraging sparsity for efficient submodular data summarization. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems, pp. 3414-3422, 2016.
Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru, and Andreas Krause. Dis- tributed submodular cover: Succinetly summarizing massive data. Advances in Neural Informa- fion Processing Systems, 28, 2015.
Baharan Mirzasoleiman, Morteza Zadimoghaddam, and Amin Karbasi. Fast distributed submodular cover: Public-private data summarization. Advances in Neural Information Processing Systems, 29, 2016.
Slobodan Mitrović, Ilija Bogunovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Volkan Cevher. Streaming robust submodular maximization: A partitioned thresholding approach. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Pro- cessing Systems, pp.
2017.
Burt L Monroe. Fully proportional representation. American Political Science Review, 894):222 940, 1995.
George L. Nemhauser and Laurence A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res., 3(3):177-188, 1978.
Ashkan Norouzi-Fard, Abbas Bazzi, Ilija Bogunovic, Marwa El Halabi, Ya-Ping Hsich, and Volkan Cevher. An efficient streaming algorithm for the submodular cover problem. Advances in Neural Information Processing Systems, 29, 2016.
Yingli Ran, Zhao Zhang, and Shaojie Tang. Improved parallel algorithm for minimum cost submod- ular cover problem. In Conference Learning Theory, pp. 3490-3502. PMLR, 2022.
Benedek Rozemberczki and Rik Sarkar. Twitch gamers: dataset for evaluating proximity preserv- ing and structural role-based node embeddings. arXiv preprint arXiv:2101.03091, 2021.
Ravid Shwartz-Ziv, Micah Goldblum, Yucen Lily Li, C. Bayan Bruss, and Andrew Gordon Wilson. Simplifying neural network training under class imbalance. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurIPS, 2023.
13

---

Published as a conference paper at ICLR 2025
Ruben Sipos, Adith Swaminathan, Pannaga Shivaswamy, and Thorsten Joachims. Temporal corpus summarization using submodular word coverage. In Proceedings of the 21st ACM international conference on Information and knowledge management, pp. 754-763. ACM, 2012.
Tasuku Soma and Yuichi Yoshida. A generalization of submodular cover via the diminishing return property on the integer lattice. Advances in neural information processing systems, 28, 2015.
Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes. Using document summarization techniques for speech data subset selection. Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp- 721-726, 2013.
Kai Wei, Rishabh K. Iyer, and Jeff A. Bilmes. Submodularity in data subset selection and active learning. In Proceedings of the 32nd International Conference on Machine Learning, ICML, volume 37, pp. 1954-1963, 2015.
Laurence A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Comb,, 2(4):385-333, 1982.
Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin. "bring your own greedy +max: Near- optimal 1/2-approximations for submodular knapsack. In The 23rd International Conference Artificial Intelligence and Statistics, AISTATS, pp. 3263-3274, 2020.
Qilian Yu, Easton Li Xu, and Shuguang Cui. Streaming algorithms for news and scientific literature recommendation: Monotone submodular maximization with $d$ -knapsack constraint. IEEE Access, 6:53736-53747, 2018
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodrigues and Krishna P. Gummadi. Fair- ness constraints: Mechanisms for fair classification. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS, volume 54 of Proceedings of Ma- chine Learning Research, pp. 962-970, 2017.
A OMITTED LEMMA OF SECTION L.2
Lemma (El Halabi et 2020 If f is monotone, then solving FSM is equivalent the problem below.
max S(5)
SEU
8.l.
ISn Ucl S ue
Ee [N]
Σ max nulld & c
B ADDITIONAL DISCUSSION
B. ADDITIONAL APPLICATIONS OF FSC
We first describe an additional number of applications of the fair submodular cover (FSC) problem.
The goal of data summarization is to find small subset dataset, such as images, documents, etc, that summarizes the dataset. Monotone submodular functions have com- monly been used in data summarization to quantify the performance of particular subset (Lin & Bilmes 2011 Lindgren et al.] 20166) and in particular SC has been used to model the data sum- marization problem (Mirzasoleiman et al., 2015)). In many of these applications, the items of the dataset can be classified into a number of categories over which balanced representation in the summary would be desirable. For example, images may be people of different nationalities, or article documents may correspond to different perspectives emphasizes maintaining a certain information threshold via the constraint f(S) 2 т, balancing cat- egories through fairness constraint, while minimizing the summary size. One particular possibility
Data summarization.
issue. The FSC formulation
14

---

Published as a conference paper at ICLR 2025
for the constraint on f is that it be nearly its maximum value, i.e., we desire summary that is as small as possible while maintaining nearly all of the information from the original dataset. We also note that data summarization motivates FSM (Halabi et al., (002). In fact, for many use cases such a formulation of FSC may be more meaningful than the alternative FSM formulation, which places emphasis on restricting the summary to particular budget.
Training data subset selection. A second application is training data subset selection in machine learning. which has previously been studied from the submodular optimization perspective (Wei
al. 2013). The fairness constraint can be used to address the problem of innacuracies introduced by class imbalance during model training, which is a major concern (Shwartz-Ziv et al., 2023). This problem can be modeled by FSC, where the constraint on the value represents requirement that the smaller training data represent the overall dataset sufficiently well therefore promoting an accurate learned model, that the training data be balanced over the classes, and we seek to select the smallest amount of training data possible training is computationally expensive.
Neural network pruning and quantization. Due the massive size of modern neural networks, large, highly-accurate models may require multiple GPUs to do the inference, which limits the usability of such models. Neural network pruning and quantization address this by reducing network size or memory while preserving performance. In this task, the goal is to select a subset of neurons while preserving network performance. One common approach used in neural network pruning and quantization is the reweighted input change pruning (Frantar et al., 2022). where the objective function has been proved to preserve weak submodularity (Halabi al. 2022). Assume that our goal is to prune the network with the objective function to achieve 70% of the value of F on the ground set i.e., F(S)= 2 0.7T, where is F(U) where U is the ground set. Additionally, a fairness constraint can ensure that neurons are proportionally selected across different layers or blocks to maintain structural balance.
Influence maximization in social network analysis. As a final application, influence maximiza- tion is an important problem in social network analysis. Suppose the social graph is described by G = (V. E, w). where V is the set of nodes with [V| = n. denotes the set of edges, and w is the weight vector defined on the set of edges F. The objective function is defined
subsets of the nodes of the graph to be the expected number of nodes influenced in the graph by a chosen seed set be an example of monotone and submodular function (Kempe et al.) 2015). In this application, FSC addresses the problem where we want to find the subset of minimum size that could influence a target fraction of nodes, f(S) 7, while ensuring faimess in node selec- tion based on associated features (e.g., demographics). This application highlights FSC's ability to balance influence spread across diverse subgroups in social networks.
S. and it is well-known
B.2 COMPARISON WITH EXISTING REDUCTIONS
In this section, we briefly discuss the difference between our reduction and the existing reduction from general submodular maximization submodular cover.
The standard reduction from an instance of submodular cover (SC) with objective f and threshold constraint 7 an instance of submodular maximization (SM) with objective f and budget k involves iteratively doing the following procedure: A guess is made for the size of the optimal solution (OPT) to the instance of SC, and this guess as the budget along with are input into an algorithm for SM. The procedure is repeated with increasingly large guesses until solution is found with f value sufficiently close r. This process is relatively straightforward since the two problems are dual to each other, and the conversion requires only a flip between the objective and the constraint. clear description of the process provided in [yer & Bilmes (2013a).
In contrast, in our fairnsss setting, the conversion from fair submodular cover (FSC) to fair sub- modular maximization (FSM) is less clear because of the more complex matroid structure of the fairness constraints. It is important to note that there is currently no existing formulation of the Sub- modular Cover (SC) problem that incorporates a matroid constraint, nor has any conversion process been developed to address such constraints. To address this, we devised a method where each guess of the size of the optimal solution for the instance of SC is used to construct an extended fairness matroid (we propose the concept of an extension to matroid in Section 1.2 This matroid is then
15

---

Published as a conference paper at ICLR 2025
input constraint into bicriteria FSM algorithm, such as those developed in Sections 3.1 and
3.2 Furthermore, post prot-psocsssing (Lines 12 in Algorithm I and Lines 7 13 in Algorithm 4) is
required for each guess to ensure the faimesss constraint is met, unlike the non-farmess setting where no such post-prcessing is necessary. A final difference between our fair setting and the general setting is that are the first to introduce converting process for multilinear extension algorithms (Algorithm{4)
B.3 COMPARISON WITH ALGORITTMM FOR SM WITH MATROID CONSTRAINTS
In this section, we provide a comparison between our fair submodular maximization algorithms and existing algorithms for submodular maximization under matroid constraints.
First, we note that the fair submodular maximization (FSM) problem can be converted into an in- stance of submodular maximization with general matroid constraint, as shown by Lemma 3 in Halabi et al. (2020). Therefore, existing algorithms for SM with a general matroid constraint can also be applied to FSM. Such algorithms return feasible solution matroid constraint, and achieve an approximation guarantee of at best 1 1/e. However, our goal with our algorithms for FSM is use them as subroutines in the conversion process, and so we develop algorithms that find sets that are better approximations to the optimal solution than 1 1/c but are not necessarily feasible. i.e., we propose algorithms for FSM with bicriteria approximation ratio. To this end, we have developed the notion of an extension of the fairness matroid (see Def- inition [ in Section 1.2p and shown that by transferring to this "bigger" constraint we can achieve better objective values. In the case of our continuous algorithm, this means traveling within an ex- tended polytope of the 8-extension of the fairness matroid. This approach enables the f value of the solution set to approach arbitrarily close to the optimal objective.
the instance of SM with
B.4 OMITTED DISCUSSION ON THE FEASIBILITY OF FSC
we present the problem definition for FSC. Notice that for some input values of т, and Pc: te- there might be no feasible solution, i.e. the instance FSC invalid. Further, it might not be casy to check whether there exists feasible solution with the value of submodular objective if to be higher than 7 and also satisfy the fairness constraint. However, if we have an algorithm that is guaranteed to produce valid, we can use this algorithm to check whether there exists an approximately feasible solution the instance not. In particular, suppose we have algorithm for valid instances of FSC that is guaranteed to produce a fair solution X such that f(X) 2 yT for some value that is close to 1. Then if we run this algorithm on the instance, we can check if the returned solution satisfies f(X) 2 yT and is fair, in which case we know there exists a nearly feasible solution. If the solution does not satisfy the guarantees, then the FSC instance must have a feasible solution at all. The algorithms proposed in this paper are examples of algorithms that provide nearly feasible solutions to valid instances of FSC. Another approach to find value for which makes the FSC problem feasible is as follows. We can choose a value of the solution set, denoted as which satisfies that gor S |1a| for each e [N], and run any non-bicriteria algorithm for the FSM instance with the faimess matroid M Mjair( (P, r. pr. qr). Since that qar < [Ucl the rank of the faimess matroid is r. Therefore, if we set to be f(S) where S is the output solution set of the algorithm for FSM, then the FSC problem would be feasible since S would be feasible set for the FSC instance.
In Section 1.2
approximately feasible solution to FSC assuming the instance is
C APPENDIX FOR SECTION 2
In this section, we present missing discussions and proofs from Section 2 in the main pa- per. We first present missing proofs of Theorem [ about algorithm convert-fair in Section C.I Then present the proof of Theorem 2 about the converting algorithm convert-cont inuous for continuous algorithms in Section C22 In addition, pseudocode for the algorithm convert-cont. nuous is presented in Algorithm
16

---

Published as a conference paper at ICLR 2025
C.1 PROOF OF THEOREM I
In this section, we present the missing proofs of the lemmas that are used in the proof of Theorem T In order prove Theorem | we need the following two lemmas. Lemma 4 guarantees that the solution set S after the rounding step satisfies the fairness constraint for cover. Lemma CommaB3imp implies the inclusion relationship
the fairness matroid with the same fairness ratios.
Lemma 4. For each guess such that K S (1 (1+a)OOPH PT), the solution set S in Algorithm 7 satisfies
BL Pals|
US < 8 9c1 1 |S| BK.
3
Proof. Here we denote the solution returned by the bicriteria algorithm for FSM S', and the solution set after the rounding steps from Line 6o Line g as S" From the definition of bicrite- ria approximation algorithm for FSM, we can see that the solution set returned by the subroutine algorithm for FSM satisfies that
S nU. S 3[
Σ max n UUl, B|pm]]] s Bx cE[N]
After the rounding steps for each group from Line to Line B the solution set satisfies that |S U.l = max [B[p< 1 for any e E [N]. It then follows that B B|pak] s 1S" I B g=ts
Since that [cE(N] max nUo, [p S BR., we have that
|S
Σ CE[N]
S nU. = Σ
max max nul. Blann) S 8K.
CE(N]
From the assumption that Σ rounding phase from Line
N ge 2 and EeE[N] min ge: ((+o)]OPPT) 2 1, after the second
10 to Line 12 have |S| 3x and that for each group c.
B Blpok| S n. S 8 [[go.].
Since the solution set S' is of cardinality BN, then we have
31 Pe|S|
U 3 9c 9c|51
B I ssnn
8
Lemma 5. For any positive integers K1, K2 such that K1 I K2, we have that
Mfair (P, N1, [pm [T)=]) S Mfair (P, 12, [pt2], [qız]]
Proof. The lemma is equivalent to prove that for any subset E Maar (P, K1, [ps 1, [g 1),
have that A is also in jaar (P, R2, [Āka]. [T )) Since & n2, IA n Uel < [e [g.k2] ]-
For the second constraint, notice that EeE[N] max{|A [] n Uel, [p }} I K1 equivalent to that
Ece[M] max(IAn Uul///
[p.ma] < 1. It then follows that
[poti]]
[p <1 Ki
Σ cE[N]
Σ
max(/AnUd//mi
12
cE[N]
Therefore, A E Mfair (P, K2, [Āna], [Tk2])
We now prove Theorem 1
Ue Theorem 1. Suppose EeeNy min min(ges B[+o)JOPTT 2 1. Then any (1. (.bBrrbicitteria approxi-
mation algorithm for FSM that returns solution set in time T(n, x) can be converted into approximation algorithm for FSC that is ((1 + +33,, biicriierii approximation algorithm that runs in time O log( (PT)) ((n, (1 + a))OPT))
log[a+1)
17

---

Published as a conference paper at ICLR 2025
Proof. Denote the optimal solution of the FSC as OPT. Since by Lemma 4 the fairesss constraint
for cover is always satisfied. When the guess of OPT satisfies that |OPT < K I (1 + PPPTT by the definition of bicriteria approximation algorithm for FSM, it follows that
f(S) 27
max X (P.n, ((oe))
f(X).
Since K > [OPT], by Lemma 5 we have that Mfair (P. fair (P, ni jis], [qh]). Therefore, it follows that
g
max X f (P.x.
f(X) 2
max P.01 f(X)
Since OPT the optimal solution of FSC, we have that [p.|OPT] < 1OPTnUdl & [qc[OPT]]
It implies that OPT Mfair(P, ( [PPT]))
Therefore we can get
max
f(X) 2 ((OPT)2*
XEM OPT) PPPP
Then
f(S) 2 YT.
This means that the algorithm stops by the time when reaches the region of ((OPT) (1 + OT)) which implies that the output solution set satisfies |S| = =Bx S 3(1 + OPP] Since by Lemma 4 the fairness constraint is always satisfied, the output solution set satisfies ((1 + 8 1 ratio. The algorithm makes O [OPT]) calls to the bicrite- ria algorithm for FSM with x = + a, ,.., a)POPT), so the query complexity is
PTT(10
O
T(n, (1 + a)))).
C.2 CONVERTING THEOREM FOR CONTINUOUS ALGORITHMS
In this section, present and analyze the converting algorithm for the continuous algorithms, which denoted as convert cont inuous. The algorithm description is in Algorithm The main result of the algorithm is presented in Theorem which restate follows.
Any continuous algorithm with a (7, -ibbriite that returns a solution time T(n, k) with probability at least approximation ratio for FSM á can converted into an approximation algorithm for FSC such that with probability 1 8, the algorithm satisfies
Theorem 2
((1 3)3, (1-35)--3) >-ierrtteria approximation ratio where (1 (1-3e y- 25 holds in expectation. The
1+3++
1+38+
query complexity is at most O (OPT)T(n, (1 ((+)))PPT)) + nolog (OPT) log 4)
OPT denote the optimal solution of the FSM. In addi- tion. we denote the optimal solution of FSM under the total cardinality λ as OPT,, i... OPT, = arg MaixxeeMM.i-PPPaa (x..). (S). First of all, notice that there are at most min (n, logi+a | 1} number guesses of |OPT] before reaches |OPT| S K S (1 + a)OPPT]. By taking union bound over all guess of OPT] would obtain with probability at least [OPT), the algorithm for FSM outputs a solution with bicriteria approximation ratio of (7, B).
Proof. Throughout the proof,
and for each guess of
Since Fxx) S n maX.e.,, f(s) S nf(OPT.), by the Chernoff bound in Lemma 8 and taking the union bound, it follows that with probability at least 1 - 5 of F(x) in Line of Algorithm 4 denoted as Y, satisfies that
2. for each guess of [OPT), the estimate
Y - Fxx) < 2=f(OPT,) + 3=F(x).
By the definition of the bicriteria approximation ratio, it follows that 2 ((1-3)))-2)(((PPT)
Similar to the proof of Theorem T
we can see that when which is the guess of the size OPT
satisfies that OPT S K (1 OPT), follows that
f(OPT.)) 2
18

---

Published as a conference paper at ICLR 2025
Algorithm 4 convert-conte inuous
Input: An FSC instance with threshold 7, fairness parameters p. g. partition P. a (7,,3)-bicritee) approximation algorithm for FSM, > 0
Output: SCU
1: A < a - 0.
2: while do
3:
- (7, -bicrtriaaa approximation for FSM with fairness matroid M (P. P. pr, Tk)
4:
Y + average over /ー log( 4a samples from F(x)
5:
if 2 {(1 3 2T then
6:
S pipage rounding of for c [N] do
7:
8:
if [S n Ucl < PaBK then Add new elements from U./5 until | 2 P.Br
9:
10:
if [|]
3K then for
[N] do while [S| < 3x and ISnU. < 9. do Add new elements in U./Sto to S
12:
14:
1 6- [11 + +
15:
return 8
Therefore, Y Y {1 3e)7 2.)r. It then follows that the algorithm stops before the guess of
[OPT satisfies |OPT n s (1 aa]OPTT] The value of multi-linear extension of the output fractional solution then satisfies
(1 + 32 F(x) 2= Y 2 {(1 (1-33)) 35) 25)T.
Combining the above inequality with that F(x) 2 (OPT).. then
(1 (1-3e)> 2:
F(x) 2
T. 1 1 35 + 2z
Since x E P(Ms), where Ma the 3 extension of the fairness matroid under the guess k. then after the pipage rounding step, we would have that S E M,. and the value of objective function satisfies
Ef(S) 2 F(x)=
(1-3))>-2;, r. After the rounding steps from Line
Line 13 in Algorithm we
1+3++
would get that the final solution set satisfies
(1 11-30 35 28
Ef(s) 2
1 35 + 28 T
3 Pc|s| $ 1S S B8 40|51
|S| S (1 + OPP)
D APPENDIX FOR SECTION 3
In this section, we present the missing content in Section 3 in the main paper.
D.1 APPENDIX FOR SECTION 3.1
In this portion of appendix, we present the missing details and proofs in Section 3.1 in the main paper, which is about two discrete algorithms greedy-fair-bs and weesholddfairnesss.
We begin by presenting the proof of Lemma 2 followed by proofs of the threshold greedy algorithm sarreshol-ffee rness-bi. Finally, the pseudocode
19

---

Published as a conference paper at ICLR 2025
of greedy-fair-bl and chreshold-fairmesss are presented in Algorithm and Al- gorithm & respectively.
First of all, prove Lemma] 2 which builds the relationship between the original fairesss matroid and its B-extension for any 8 N+.
Lemma 2 For any 3 E N+ and any fairness matroid Mair (P, k. I, iT), denote Mg as the B- extended fairness matroid of Marr (P, K. ú). Then for any set S Mg with |S| BR, T Mfair (P, n. I ()) with [T' = K, and any permutation of S = ($1, $2, .... 8Bx). there exist a sequence E = (e1, .2..... eBx) such that each element in ' appears B times in E and that
S: U (et+1 EM,
Vi E 10.
where St = ($1, 82 .... 9.) and So
Proof. Before proving the lemma, we define some notations here. For any sequence of any length m denoted as A = (a1, a2 .... am), ) we define the number of element in the sequence as |A* i.e., |Aa| := [i: a, = =}}. In addition. we define the number of elements of group as 14% i.e., |
the sequence
(i E U= ExEU. |A% For the sequence F, we denote the sequence containing i-th element to the last elements as E,, i.e., E, = (e,, Cit, Cgx). Now we prove stronger claim which would imply the results in the lemma.
Claim 1. For any 3 E Nt, denote Ma as the B-extension of the fairness matroid. Then for any sel S E M&, there exists a sequence F. (e1, BBx) such that for each i E {0, 1,.., 3x), the sequence F, (St, E.+1) ($1, $2, .... 84: ci41.... EBa.) satisfies that
F S 3
VCE [N]
Σ max (1F 1
103) S BE.
cE[N]
Here for each E, we have T. Besides, have that for any element T,
F < B.
We prove the claim by induction. First, when = 3R. F. Since E Mas, the claim holds. Suppose the result in the claim holds for i, and we prove the claim for i 1. There are two cases.
Case There exists some group co such that [,,,-,, 1 S leg 1. Since T i. ' n Uel > Le for each E [N]. Therefore, in this case, there exists least one element x E Ucg n such that [(S 1 < 3. Then choose & = x and E, = (2, E++ 1), the results in the claim will be satisfied.
Case 2. For all group E [N], ((S,-1, F4+119 1.9. Since the sequence (S,-1, Es+1) is of length BK - 1, we have that
I(S:,1, E++1)l l < BR S TT
Therefore, there exists at least one group c such that [(S 1 < [T Uz, 13. (Otherwise Eee(N] [S 14 > >> U. = Bk, which breaks the assump- tion.) From [(S,-, F < [T n Ue, 18, we have that there exists at least one element x E T Ue, such that
S B
Then we set the i-th element in F. to be x, then F, = (x. E.41). It follows that (S, E,)a < 3. For each element x' E T/(x) [(S E,)=² (S 1= 1 33
Since e; = x E Ue,, For group e * C1. [(,,-1, E.) = E < ugB
E
by the assumption that the claim holds for iteration For group C1. (,)
(, El +1 < u.B. Since for all group E [N], [(S,-, E+1 2 4,3, it follows that ((S-1, E
1 L.3. Thus
Σ [E[N]
max E.)9,1883 = Σ 1(S)-1, F.)9
20

---

Published as a conference paper at ICLR 2025
(S,,-1, E,)l BR.
Thus we prove the claim for iteration i - under the assumption that the claim holds for i. By induction, the claim holds for all For 0, (Sp. Eb) E. From the construction of E we have that [&] = 3k, and that | = 3 for all T. Since for each group e, we have |S; U (e1+1) n Ucl S [(S,, B.)% From the result in the claim, we can prove that S U {e+t1) MM.
D.1.1 PROOF OF THEOREM
Theorem 3. Suppose that greedy- fordy--faineess -bi is run for an instance of FSM, then greedy-fai rness-bii outputs a solution S that satisfies a (1 -1 E, biccriiia approximation guarantee in at most O (nk/E) queries of
Proof. Denote the optimal solution of (e S(S) as OPT, i.c. OPT
arg max seM S(S). Since by Lemma we have M1/e Mfair (P, k/ee s/ee, ū/e)
matroid of rank 8/E, then the Algorithm ends after k/c steps and the output solution set satisfies [S| k/e. Since S M1/e. then
[Snudl S ue/e VCe [N]
max (1SnU.ble/e) & k/e. cE(N)
Then it remains to prove that f(S) 2 (1 (OOP)) From Lemma 2 we know that there exists a sequence E that contains 1/e copies of OPT and that each step i, St U (e4t1 E MM1s-- Then by the greedy selection strategy, we have
[(S+1) ((S)) 2 [(S; U
Thus by submodularity, we have
I(S++)) S(S:) 2 S(S U ((4+1) - [(S:) AS(S, e.1).
Summing over all i, we would get
h-1
Σ (18+1)-((SS)
Σ Af(S,e_1).
Since the sequence E contains 1/c copies of each element in OPT, then Σ Af(S, 1/2 Encorr Af(S.0). Since
Σ f(S.+1) f(S.) f(S) f(0) and that f is nonnegative,
Σ AS(S,0) f(OPT) - f(S)
S(S) 2 Σ
E
1=0
oEOPT
Thus we have
f(S) 2 I+E
f(OPT) 2 (1-c)f(OPT).
D.1.2 PROOF OF THEOREM 4
Before we present the proof of the theorem, first we present the proof of the following lemma. Let us denote the solution set after the i-th element in threshold So--farree faiirnsss--eee as S. By Lemma
2. we know that we can construct sequence E (e1, 62, Cx/s) that contains 1/e copies of OPT
and that S; (c++1} E M1/s- Then we have the following lemma.
21

---

Published as a conference paper at ICLR 2025
Lemma 6. For any 0 S i < K/E, follows that
Af(S, 2 (1-s)Af(S), - Ed/r..
Proof. First, we consider the case 8:+1 is added to the solution set and is not a dummy variable,
it follows that AS 8(+1) 2 Since S, U {ee+1] Mi/es then if e1+1 & S; by submodularity
we have (S, 6i-1) I r/(1 e). If 6i+1 E S; then Af (141) = 0 S 7/(1 - -). Next, dummy variable, then AS(S, 8(41) = 0. c E S, then Af 1++1) = 0 and the above inequality in the lemma holds. If If $ S₁ since Sky U [eit1)
we consider the case if 8;41
M1/er then Af(S,, 1++1) 2 ed/K. Therefore, we have that
AS 8441) 2 (1 - e)Af(Si, e441) - Ed/k.
Next, we present the proof of Theorem
is run for an instance of FSM with E E 10. Then threshold-fairneseee faiesss-bbr outputs a solution that satisfies (1 25, ))- bicriteria approximation guarantee in most O (n/slog(n//) queries f.
Theorem 4. Suppose that faressoiid-farnesssee
Proof. First, notice that the (eoorithh@@ends in at most (1/e) log(k/e) number of iterations. There- fore, there most n/e log(s/e) number of queries f. Next, prove the bicriteria approxi- mation ratio of thresholde sochold-aa reiiinnessbi From the description of Algorithm 6 we have that the output solution set S E M1/e. then
|SnUd S un/s max (IS n Uclsb//e S k/e. <E(N]
AeE [N]
It remains to prove that f(S) 2 (1-2s)
where OPT is defined as the optimal solution of FSM, i.e., OPT = arg max SeMM (SS). For simplicity, we assume the returned solution has size [S| k1. As discussed in the proof of Theorem 3 Rank(MM1/e) =k/s. Here we denote the solution set as S = (81, Su., Sn/s), i-th element added to the solution set. In the case when the threshold drops below ed/n at the termination and K1 S K/E, we can add dummy elements S such that |S| = K/E. By Lemma 6 we have that there is sequence E = (El, E2, c2..... ek/e) that contains 1/E copies of PT and
and we define S; as S ($1.... s;). Here is the
....
A Af 8141) 2 (1- =))(((()))))) - -Ed/K.
Thus by submodularity, we have I(S++1)= - ((S.) 2 (1 (1
(1- ed/R.
Summing over all i, we would get
k/c-1
8/c-1
Σ
[(S++)) - ((S)) 2 (1 (1-e)
Σ t=0
AS(S, ei+1 - d.
1/8 copies of each element in OPT, then Σ AS e(1)) 1/e EosopT AS) Since Σn f(S++1) - ((S:) = S(S) -((0) and that f is nonnegative,
Since the sequence E contains
k/c-1
S(S) 2 (1 -1))
AS(S,ei+)) -d
t=0
(1 (1-6)
Σ AS(S,0) -d
3 оЕOPT
1 (11-)) - -
22

---

Published as a conference paper at ICLR 2025
Algorithm 5 greedd-fairress
1: Input: E, fairness matroid M Maain(P,,, (,,
2: Output: S E U
3: S 5-U 0
4: Denote Maai [ (P/ M1/E
5: while Ez s.t. SU {2) E Mife do
6:
V f USS (x) E M1/+))
7: 4 arggrmax Af
8:
Su
return S
Algorithm
1: Input: e, fairesss matroid M M i,
2: Output: S EU
3: St0 0
4: Denote MMair(P,K/el [/e, ū/E) as M1/e
5: d + (a) f({z})
6: for T = ed/k; + 7(1 5) do
7: for do
8:
if {2) Mi/s and Af 2 then
9:
S (z}
10:
if i| = x/E then
11:
return S
return S
> -1 200-))
By re-arranging the above equation, we have that
S(S) 2 - (1-2))
D.2 APPENDIX FOR SECTION 3.2
In this section, we provide the omitted content from Section 3.2 of the main paper. Specifically, present the proof of Lemma 7 which offers the theoretical guarantee for the subroutine algorithm wwweaaiingttheeshhlle of the Lemma is as follows.
the continuous algorithm cont-bi. The statement
Lemma 7. During each call of orgerresiing-hhreeooo.pppoooooc the output coordinate set B satisfies that
F(x + cl -(x)) 2 ((In(1/))+ (1(())+))(O)))((P)))) F(x + =ll))
Proof. For notation simplicity, we denote the rank of the matroid Min as m. i.c., m = (In()) + 1)x. Here we denote the output solution set as B {b), by.. 6m3 where is the i- th element that is added to set B. Here if B < m, then for any i > |B]. b, is defined as a dummy Since M J+1 is an In + 1-extension of the original fairness matroid, then by Lemma 2 there exists a sequence = (ei, 62, .... cm) such that E contains In(1/e) + 1 copies of the optimal solution OPT {01, 02, ..., 0x} such that B, U (e+) e Mm for each E [m].
variable. addition, we define B, = {b,, be.
Notice that by Lemma we have that with probability at least t for any fixed x + 1 and 4n
fixed element u, the empirical mean X {B, u), which is the average
35 22 log samples of the
23

---

Published as a conference paper at ICLR 2025
random variable X A u) satisfies that
[x(B,,)) ( a)1 5 R
((OPT) +BAT()5(XX((XXX + =l..).).
Since during the execution of cont-bi, there are at most 2 log(k/E) such estimations, by applying the union bound, we have that with probability at least 2 the inequality (1) holds for each x, 1,, b,) 2 I-e or at the last iteration, we have that Since
B and u during cont-bi. From the description in Algorithm 3 we can see that X (B,-1,
w. For the element 6; we have that (,) S
w
(B) & ed x Therefore, we have that (B; by) 2 (1 - (B, OPT = MasseMMaar(PM...... [(S) 2 d, it then follows that
3s S(OPT).
(1 + + 1.),), 2 =){EA((S(x el (.e)))
k
By rearranging the above inequality and simple calculations, we have
38 4 2 - f(OPT).
By the construction of set B, would get
m
F(x+#18) F(x) Σ F(x+ F(x -(x
OF bb.
s=x+1a,_1
BAf(S(x + ElB.
3e ((P(TPT)
2 8
35 [( 1):;)
E11
3e)
3:" (In
+ +1)((PPT)
2 E1 - 3e)
[Af(S(x+5ln))
32 (In(
+ +))(OPTT)
where the last inequality results from the submodularity of f. From Lemma 2
we have that
F(x + +al)) - F(x) 2 E(1 3e) ( 1) EAf(S(x+elg).oo
3ce - 1))((PP))
2 6( (61133) 33) +)[[(TPPT)
F(x+ell)) -
-3=70m(+)-1))0000
2 -(t -(x+e)))))
24

---

Published as a conference paper at ICLR 2025
D.2.1 PROOF OF THEOREM
Theorem S. Suppose that Algorithm 2 run for an instance of FSM, then with probability at least 1- . cont tetttthresh-ee -eeedy bi outputs a solution S that satisfies (1 - Te, In(?) + 1)-
bicriteria approximation guarantee in most O ( In (n/s)) queries of f.
Proof. First of all, from the description of the subroutine algorithm DTP in Algorithm 3 we can see that there are most log(k/s)/e number of iterations in the outer for loop. Therefore, the subroutine algorithm DTP takes at most O(" nw (n./n(n/)) In(x/e)). Since there are at most calls to DTP, we can prove the sample complexity.
6a
Next, we prove the bicriteria approximation ratio. By Definition [ it is equivalent to prove that X P(M and F(x) 2 (1 7E) f(OP)) Denote 8 to be the output set of the t-th call to the subroutine algorithm DI2. Then it follows that the output solution set of cont-bi can be denoted as x Σl a1 p(o)- Since ((a) E M. we have that 189 E P(Mm((/e)+1) By the fact that P P(MMm(1/e)=1)) is convex, we have that x E P(Min(1/e)1)). Denote the fractional solution x after t-th step as X2, then by Lemma 7 we have
F(x++1)= F(x,) 2 e (In(1/e) + ()((1 (e))( F(xx+1)).
For notation simplicity, we define L = s(ln - l]. It then follows that
F(x.) L(1 (OPT(
F(x++1) 2
1
Since there are 1/8 iterations in cont-bi, the output x satisfies that X1/c- By applying induction to the above inequality, we would get
F(X1/e) 2 (1 (1 (1+1) (()
2 (1 c (1-
vv (1 - - (s)
N (1 70)
Observe that compared to greedy-fair-bl and threshold-fai fiw-ffarnnessbi... our proposed algorithm cont -bi demonstrates an enhanced approximation ratio for the cardinality of the output solution set, improving from O (()))) to ((n(11e)) This improvement is achieved while maintain- ing the same order of function value violation, specifically f(() 2 (1 ((e))[(OPT) However, this enhancement requires an increased number of queries. This suggests the potential for attaining comparable approximation ratios for the submodular cover problem under specific types of matroid- type constraints.
Corollary 5.1. Using the Algorithm 3 aa the subroutine for the converting algorithm in Algorithm we obtain an algorithm that achieves an approximation ratio of ((1 + a)) (n()) + O(e)) in
at most ( m(1+a)]OPP] log"(: log [OPT) with high probability.
Proof. The result of the approximation ratio can be obtained by combining Theorem and Theorem 5 together. Here we provide proof of the sample complexity. Notice that for each guesses of OPT of cardinality Kg. the algorithm cont-bi that runs with the input M Maär (P, Kig. p.t.. ūngg) uses at
most ( nig log (2)
From the result in Theorem and Theorem the total number of sample
g+
complexity would be O( ((((++a])OPP) OPT] log" (P) log OPT
24a
E PROOF OF TECHNICAL LEMMAS
Lemma 8 (Relative + Additive Chernoff Bound (Lemma 2.3 in Badanidiyuru & Vondrák (2014)). Let X1,.., XN be independent random variables such that for each i, X E [0, R] and E[X,] = for all i, Let X 1/4 EN X,. Then
Nae
P(L - n1 > +e < 2exp
3R }.
25

---

Published as a conference paper at ICLR 2025
F GREEDY-BI ALGORITHM
Algorithm 7 greedy-bi
1: Input: T
2: Output: S EEU U
3: S 0
4: while f(S) 1 < (1-E)T do
5:
< arg max Af
6: S 5 (u)
return 5
G ADDITIONAL EXPERIMENTS
G.1 IMPLEMENTATION
Maximum Coverage. In maximum coverage problems, the objective is to identify of fixed nodes that optimally maximize coverage within a network or graph. Given a graph where V and F respectively represent the set of vertices and nodes in the graph. Define function N : V + 2V as (v) = {u, (u, v) E F}, which represents the collection of neighbors of node v. Then the objective of this maximization problem can be defined as the monotone submodular function f(S)= Uves N (v)].. The dataset utilized in our maximum coverage experiments include Twitch and the Twitch.5000 of Twitch Gamers, which is a uniformly sampled subgraph of the Twitch Gamers dataset (Rozemberezki & Sarkar (021), comprising 5,000 vertices and 2,000 vertices (users) who speak English, German, French, Spanish, Russian, or Chinese respectively. We aim to develop solution with a high value exceeding a given threshold while ensuring fair balance between users who speak different languages.
(V, E),
Set Covering For the datasets annotated with tags, the objective of set covering is to extract diverse subset that maximizes the objective function f(S) Uxes t(x),, where the function maps an element æ in set N to its corresponding tags 1(x). The dataset employed in our set covering experiments is subset Corel5k Duygulu et al. (2002). For each item in the dataset, we randomly added category from {0, 2, 3, 4, 5) with probability of 0.5. Any item not assigned random category was assigned category 1. By ensuring a balanced distribution solutions across categories, we aim extract representative set with high? f value that surpasses given threshold T.
Experimental setup for max coverage. We implement proposed algorithm two different instances, including the Twitch 5000 dataset and Twitch 2000. The algorithms implemented in- clude convert-fail leveraging two subroutines provided in Appendix D greedy- faieddy-fiii r-bi (Algorithm 5 referred to as "GREEDY-Fair") and referred as "GrrEDY-Fair",. On the relatively small dataset Twitch we also imple- ment convert-core in inuous using cont-br as the subroutine ( referred to as "CONTI- Fair"). Due to high query complexity of the continuous algorithm cont-bi, we evaluate convert-continuuus heuristically by taking 5 samples per estimation in Line 8 of the We compare our approach to the greedy baseline,
(Algorithm 6
greedy-bi, provided in Appendix
To ensure a fair comparison based on the quality of the solutions, we use different default values for the parameter in each algorithm. This is because each algorithm has varying approximation ratio. Specifically, we set greedy-fair-be (where C is the number of groups). For threshold-fairnssee All the experiments i7- 17-13700 CPU, 32GB of RAM, and Ubuntu 22.04.3 LTS. Each experiment with one set of parame- ters can be done in 120 seconds.
0.1, a = 0.2, ue = 1.1/C,4o 0.9/C for greedy bi and
use & = 0.05 while keeping the other parameters the same.
conducted
single machine equipped with 13th Gen Intel(R) Core(TM)
26

---

Published as a conference paper at ICLR 2025
G.2 EXPERIMENTS SETUP FOR SET COVERING.
We implement our proposed algorithm convert-fall leveraging two subroutines provided in Appendix D greedy-faii
(Algorithm 5 and thresholldfaiimess (Algo- rithm 6). We compare our approach to the greedy bascline, greedy-bi, provided in Appendix F
To ensure a fair comparison based on the quality of the solutions, we use different default values for the parameter in each algorithm. This is because each algorithm has varying approximation ratio. Specifically, we set greedy-fair-be (where C' is the number of groups). For threshold-faireesee use 0.05 while keeping the other parameters the same.
0.1, a 0.2, th 1.1 1.1/C,le 0.9/C for greedy-bi and we
All the experiments are conducted on single machine equipped with 13th Gen Intel(R) Core(TM) 17-13700 CPU, 32GB of RAM, and Ubuntu 22.04.3 LTS. Each experiment with one set of parame- ters can be done in 30 seconds.
0.9 00000000
0:15
0:15
0.10
0.10
(a) greedy-bl
(b) greedy-fairness--t
(c) (httresholddfalleeees faes---rreeebbll
300
Fairness difference
240
GREEDY-Fair
0.60
THRES-Fair
180
75
GREEDY
GREEDY-Fair
120
GREEDY THRES-Fair
0.30
60
0.15
Value the given threshold
Value of the given threshold
Value of the given threshold
(d) f
(e) Cost
(I) Fairness difference
Figure 2: Performance comparison the Corel dataset for Set Covering. 2a 2b 2c illustrate the
distribution of images across various categories in the solutions produced by different algorithms with 7 300. f: the value of the objective submodular function. Cost: the size of the returned solution. Fairness difference: (max, |S Ucl min U.I)/[SI
G.3 RESULTS
G.4 RESULTS ON COREL DATASET
2b and 2c showcase the distribution of images across various categories in the solutions produced by these algorithms with 300. Figures 2e and present the performance of these algorithms (f value, cost, and fairness difference) for varying values of r. As shown in Figure 2a with T = 300, over 70% of the pictures the solution returned by greedy bbi are labeled as cate- gory 'I'. While the solutions produced by greedy fair bi and threshold fa rness bi exhibit way fairer distributions across various categories as shown in Figures 2a and 2bb.. Similarly, the value of given increases, the magnitude of this difference also increases (see 2f Figure 2d showcases that for all these algorithms the objective function value f(S) scales almost linearly with the threshold 7, which aligns with the theoretical guarantees of the approximation ratio.
Figures 2a
27

---

Published as a conference paper at ICLR 2025
GREEDY-Fair
GREEDY
450
CONTI-Fair
75
THRES-Fair
GRirDY-Fair
GREEDY
50
150
COit
Value of the given threshold
Value of the given threshold
(a) f
(b) Cost
Figure 3: Performance comparison on the Twitch 2000 dataset for maximum coverage. "CONTI- Fair" corresponds to the convert-fall fair algorithm using cont-bi as the subroutine. f: the value the objective submodular function. Cost: the size of the returned solution. Fairness differ- ence: (max. [S Ua| mine JS U.ll/SS
Notably, unlike the results presented in Section our proposed algorithms achieve comparable costs to the greedy-bi solution (as shown in Figure 2e on the Corel5k dataset. This is likely because the Corel5k dataset is less biased and the marginal gains for adding different elements are more uniform, compared to the Twitch Gamer dataset.
G.5 RESULTS ON THE 2000 DATASET
The results of comparing different algorithms on the Twitch dataset are presented in Figure 3a under faimess constraints, the continuous algorithm CONTI- Fair achieves a lower cost compared to the discrete algorithms, GREEDY-Fair and THRES-Fair aligning with the theoretical guarantees presented in the main paper. However, CONTI-Fair incurs a higher cost than the greedy algorithm without fairness constraint, potentially due to the limited sampling (five samples per estimation) of the multilincar extension Line falls short of the theoretical requirements.
and 3b From the results,
8 in Algorithm which
28


Reviews:
[{"review_id": "iSuZof3fjp", "reviewer": "Reviewer_6Qua", "summary": "This paper addresses the fair submodular cover problem, where a submodular function is defined over a set of elements that are divided into disjoint classes. The objective is to select a minimum number of elements such that the selected subset meets a target submodular value threshold and the number of selected elements of each class is within a predefined interval.\n\nAlthough prior work has addressed fair submodular maximization, fair submodular cover has not been previously studied. The authors first provide a reduction from fair submodular maximization to fair submodular cover. It is worth noting that there was a reduction for the non-fair case, which does not directly apply here. Additionally, they develop new algorithms for fair submodular maximization, achieving improved results when applied within their reduction framework. For designing those algorithms, they leverage the result by El Halabi et al. (2020), which converts instances of fair submodular maximization into submodular maximization problems under matroid constraints.", "questions": "- Could you clarify the technical differences between your reduction from fair submodular maximization to fair submodular cover and the standard reduction used in the non-fair setting?\n- How do your algorithms for fair submodular maximization differ technically from previous approaches for submodular maximization under matroid constraints, particularly the one based on the multilinear extension?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors present the first known algorithm for fair submodular cover, which achieves a near-optimal approximation ratio close to that of the greedy algorithm for the non-fair version, with the added benefit of increased diversity in the selected elements. Also, the paper includes experimental results that support the practical effectiveness of their proposed methods and highlight the benefits of their approach in selecting diverse elements across classes.", "weaknesses": "The difference between the authors' reduction and the existing reduction from general submodular maximization to submodular cover could be elaborated on further. This distinction is somewhat unclear, and understanding the technical differences would enhance the clarity of their contribution.\n\nThe paper could benefit from a more detailed comparison between their fair submodular maximization algorithms and existing algorithms for submodular maximization under matroid constraints, especially for their best algorithm which is based on multilinear extension that already has been used for submodular maximization.\n\n## Minor comment:\nIn lines 200 and 206, you use $U^c$ but I think $U_c$ is the correct one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uneMUiORlQ", "reviewer": "Reviewer_MRoR", "summary": "The paper studies the fair submodular cover problem. In this problem, we are given a set of ground elements and a monotone submodular function defined over them. All ground elements are partitioned into $N$ groups, each group $c$ having a corresponding interval $[p_c,q_c]$. The objective is to select as few elements as possible such that the value of the submodular function is greater than or equal to a given threshold $\\tau$, while ensuring that the proportion of selected elements from each group falls between $p_c$ and $q_c$.\n\nThe authors consider bicriteria approximation algorithms, where the threshold constraint may be violated by a factor. By establishing a relationship between fair submodular cover (FSC) and fair submodular maximization (FSM), they show that given a $(\\gamma,\\beta)$-approximation algorithm for FSM, they can convert it to an algorithm for FSC with an approximation ratio of $((1+\\alpha)\\beta, \\gamma)$. if the given FSM algorithm is continuous, they can yield an approximation ratio of $((1+\\alpha)\\beta, ((1-3\\epsilon)\\gamma-2\\epsilon)/(1+3\\epsilon +2\\epsilon/\\gamma))$. Furthermore, they present nearly feasible algorithms that can admit $((1+\\alpha)/\\epsilon, 1-O(\\epsilon))$-approximation and $((1+\\alpha)(\\ln(1/\\epsilon)+1), 1-O(\\epsilon))$. Finally, the proposed algorithms are investigated experimentally.", "questions": "See the weakness above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The fair submodular cover problem makes sense. The paper makes theoretical contributions. A nice relationship between FSM and FSC is established in the paper and several bicriteria approximation algorithms are proposed. The high-level algorithmic ideas are clean.\n\n- Both theoretical analysts and empirical evaluations are provided.", "weaknesses": "- The problem certainly holds theoretical interest. However, I am a bit concerned about whether it will engage the ICLR community. Could the authors provide some real-world applications?\n\n- The authors did not compare the empirical running time of the proposed algorithms with the baselines. The theoretical running time looks horrible, so I wonder how long these algorithms will take in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2DwTutgDQU", "reviewer": "Reviewer_WbLT", "summary": "This paper studies a variant of the classical submodular cover problem, in which, given a monotone submodular function, the goal is to pick an element set with the smallest size so that the value of this set is larger than a given threshold. This paper studies the fairness version of the problem, in which the ground element set is partitioned into k groups, and each group has an upper $u$ and lower bound $l$. A fair solution should pick at least $l$ elements and, at most, $u$ elements from each group. The goal is still to pick a fair solution with a minimum size such that the value of the picked set is larger than a given threshold.\n\nThe main contribution of this work is a bicriteria algorithm that achieves $\\ln n$-approximation with a slightly violating fairness constraint. This is the essentially best possible since the classical submodular cover admits the set cover problem as a special case.", "questions": "I don't have any specific questions.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The studied problem is theoretically interesting and the presentation of this paper is clear. I appreciate that the authors give an intuitive description, which helps understand the algorithm's high-level idea.\n\n2. The obtained results are almost tight for a bicriteria approximation. Based on my knowledge, these kinds of fairness constraints (upper and lower bounds for each group) always improve the difficulty of a problem a lot. It is reasonable to study the bicriteria approximation in this case.\n\n3. The authors also include the experimental result for the set cover instance, demonstrating the proposed algorithms' efficiency.", "weaknesses": "1. The studied problem is theoretically interesting, but it is a little incremental. One needs to provide convincing motivation for the problem. It looks that the studied problem only adds an extra constraint to the classical submodular cover problem. The introduction section does not give a specific motivation for the studied problem.\n\n2. There is no lower bound known in the paper. Namely, there is no lower bound for the bicriteria approximation. This may not be a big problem since these fair constraints are usually hard. But, one still needs to show how good is the trade-off obtained by the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qqs0nivXUD", "reviewer": "Reviewer_pFnE", "summary": "This paper studies the submodular cover problem under the fairness constraint (FSC). The authors propose two algorithms, convert-fair and convert-continuous, which exploit the dual relationship between Fair Submodular Maximization (FSM) and FSC to transform bicriteria approximation algorithms for FSM into ones applicable to FSC. Next, they propose three algorithms for FSM that, when combined with their converting algorithms, produce approximate solutions for FSC. The discrete algorithms achieve approximation ratios of $(1 - O(\\varepsilon),\\frac{1}{\\varepsilon})$ for FSM, while the continuous algorithm achieves a better ratio of $(1 - O(\\varepsilon),\\ln(\\frac{1}{\\varepsilon}) + 1)$ but needs more queries. By integrating these algorithms into their framework, they obtain improved FSC algorithms with better approximation ratios. The continuous algorithm for FSM with the converting algorithm achieves a $((1 + \\alpha) \\ln (n) + 1, 1 − 7/n)$ bicriteria approximation guarantee for an instance of FSC when  $\\varepsilon = \\frac{1}{n}$, which is close to the lower bound.", "questions": "* What are the motivations for FSC, e.g., real-world applications?\n* Compared to the conversion algorithms without fairness constraints, what is the novelty of the conversion algorithms proposed in the paper?\n* In Theorem 2, the approximation ratio $\\frac{(1 - 3\\varepsilon)\\gamma - 2\\varepsilon}{1 + 3\\varepsilon + \\frac{2\\varepsilon}{\\gamma}}$ 'holds in expectation'. Is it sufficient to guarantee that the solution provided by the algorithm is close to feasible with high probability?\n* The continuous algorithm proposed in the paper theoretically outperforms the discrete algorithms, while the experiments only showcase the performance of the discrete algorithms. Are there any experimental results available for the continuous algorithm?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The proposed algorithms are easy to follow.\n* The proposed continuous algorithm approximately matches the theoretical lower bound, demonstrating its efficiency.", "weaknesses": "* The motivation for considering FSC is unclear. The authors only say that FSM has been well studied while FSC has not. This can not be a good motivation. \n* The experiments demonstrate the advantages of the discrete algorithms on the FSC problem compared to the standard greedy algorithm; however, the solutions obtained by the discrete algorithms include many more elements. Moreover, the experiments lack the presentation of the effectiveness of the continuous algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)