An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
Authors: Fabian Christian Spaeh
Atsushi Miyauchi
Venue: ICML 2025 poster (2025)
Keywords: submodular maximization
multiobjective
max-min fairness
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: We provide a new and efficient approximation algorithm for multiobjective submodular maximization

Abstract: Maximizing a single submodular set function subject to a cardinality constraint is a well-studied and central topic in combinatorial optimization. However, finding a set that maximizes multiple functions at the same time is much less understood, even though it is a formulation which naturally occurs in robust maximization or problems with fairness considerations such as fair influence maximization or fair allocation. In this work, we consider the problem of maximizing the minimum over many submodular functions subject to a cardinality constraint, which is known as multiobjective submodular maximization. All known polynomial-time approximation algorithms either obtain a weak approximation guarantee or rely on the evaluation of the multilinear extension. The latter is expensive to evaluate and renders such algorithms impractical. We bridge this gap and introduce the first scalable and practical algorithm that obtains the best-known approximation guarantee. We furthermore introduce a novel application fair centrality maximization and show how it can be addressed via multiobjective submodular maximization. In our experimental evaluation, we show that our algorithm outperforms known algorithms in terms of objective value and running time.

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
Fabian Spach Atsushi Miyauchi?
Abstract
modular objective f(S) is maximized. Applications range from welfare maximization to experimental design and vi- ral marketing via influence maximization (Bilmes, 2022; Kempe et al., 2003; Krause & Guestrin, 2007). Maximizing a single monotone submodular function is well understood, and the greedy algorithm is practically efficient and obtains the best possible polynomial
Maximizing a single submodular set function sub- ject to a cardinality constraint is well-studied and central topic in combinatorial optimization. However, finding set that maximizes multiple functions at the same time is much less under- stood, even though is a formulation which natu- rally occurs in robust maximization or problems with fairness considerations such as fair influence maximization or fair allocation. In this work, we consider the problem of maximizing the mini- mum over many submodular functions, which is known as multiobjective submodular maximiza- tion. All known polynomial-time approximation algorithms either obtain a weak approximation guarantee or rely on the evaluation of the multi- linear extension. The latter expensive to evalu- ate and renders such algorithms impractical. We bridge this gap and introduce the first scalable and practical algorithm that obtains the best-known ap- proximation guarantee. We furthermore introduce a novel application fair centrality maximization and show how it can be addressed via multiob- jective submodular maximization. In our exper- imental evaluation, we show that our algorithm outperforms known algorithms in terms of objec- tive value and running time.
approximation guarantee of 1 - R 0.63 (Nemhauser & Wolsey, 1978). Moreover, so-called lazy evaluations make the greedy algorithm highly scalable (Minoux, 2005).
Another line of work studies the task where k different sub- modular objectives have to be simultancously maximized, which is called multiobjective submodular maximization. This also important for many applications. For instance, in robust experimental design, the goal is maximize sub- modular function fe. which depends on a-priori unknown parameter 0 (Krause et al., 2008). One seeks to find set that maximizes fa simultancously for all valid parameters 6. Recently, many applications in artificial intelligence con- sider the max-min fairness objective, which often naturally falls into the multiobjective scenario. One such example fair influence maximization, where the goal is to maximize the influence among all groups (Tsang et al., 2019).
Even though applications for the multiobjective setting are numerous and relevant, solving the problem with theoretical guarantees still presents challenges for current algorithms. Indeed, the prior work can be split into two categories of approximation algorithms: First, there are algorithms that cannot recover the (1 )>aappooxmmatinn but are discrete and efficient in practice. The best approximation ratio for such an algorithm is (1 - _ z 0.40 (Udwani, 2018). Sec- ond, there are algorithms that (almost) recover the (1 - 4)- approximation guarantee (Chekuri et al., 2010; Udwani, 20, but solve a continuous relaxation of the problem based on the multilinear extension, which is known to be impractical (Bai et al., 2018; Chen & Kuhnle, 2024; Buch- binder & Feldman, 2024). These algorithms do not scale to larger problem instances, as the ones necessitated by the mentioned applications.
1. Introduction
Due to the natural diminishing returns property, maximiz- ing submodular functions is a central task in various fields such optimization, machine learning, and economics (Fu- jishige, 2005; Nemhauser et al., 1978). In submodular maxi- mization subject to cardinality constraint the task is to find a set S of size |S| < B for some budget B such that sub-
'Boston University, Boston, USA *CENTAI Institute, Turin, @ Italy. Correspondence to: Fabian Spach <fspach@bu.cdu>, bu.edu>, At- sushi Miyauchi satsushi.mmyaueee @centai.cu>>
This is where our work comes in: We introduce an algo- rithm that (almost) achieves the (1 - ---aproxximtionn, but does not relax the problem to the continuous setting and
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

An Asympiotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
is therefore efficient in practice. This settles an open ques- tion of Udwani (2018), showing that there is practically efficient algorithm that obtains best possible approximation ratio. Our main contributions are the following:
even moderately sized problems, as we can generally only approximate the relaxation via sampling. In their seminal work, Chekuri et al. (2010) introduced the oblivious round- ing scheme Swap Rounding and showed how this leads to an al ggorithm for the multiobjective problem even subject to a matroid constraint. Later, Udwani (2018) introduced a more efficient algorithm for cardinality constraints. Tsang et al. (2019) gave an algorithm that finds a continuous solution via Moole, and they showed that the multilinear extension can be evaluated efficiently for influence maximization.
1. We introduce a novel algorithm for multiobjective submodular maximization. Our algorithm (almost) achieves the best possible approximation ratio of 1 - - Our algorithm is vastly more efficient than algorithms with comparable guarantees, which rely on a contin- uous relaxation and rounding procedure. Our al- gorithm, instead, achieves its guarantee via a novel concentration argument.
The second type of algorithm avoids evaluation of the multilinear extension and only operates on discrete solu- tions. Udwani (2018) also introduced an efficient (1 - 2 approximation algorithm via MWU. The algorithm main- tains vector of weights y E Sc, where C is the index set of multiple submodular functions and Ac is the probabil- ity simplex over C, and uses a subroutine that solves the problem of maximizing the combined submodular function Eceo (eS). The weights are then updated based on the individual values achieved for each objective. However, combining the solutions created in each iteration introduces an additional factor of 1 into the approximation guaran- tee, which is the reason that this algorithm does not retain the guarantee of continuous algorithms. Orlin et al. (2018) devised a combinatorial algorithm that almost achieves the (1 - -apppoxxmmaiion but only for the case when A < 2.
2. Furthermore, we show how multiplicative weights up- dates (MWU) can further reduce the number of func- tion evaluations, which also yields an analogue to the lazy greedy algorithm for the multiobjective problem.
3. We introduce a novel application fair centrality maxi- mization, generalization of the well-studied task of centrality maximization with faimess consideration, and show how it can be formulated as a scaee multiobjective submodular maximization.
4. We experimentally verify that our algorithm outper- forms previous methods in terms of objective value and running time. The practical efficiency of our method allows us to be the first to solve large-scale instances while retaining quality of solutions.
Other efficient algorithms use the greedy paradigm, but do not obtain constant factor approximation guarantees. The aforementioned bi-criteria algorithm by Krause al. (2008) maximizes modified objective function, but may violate the budget constraint in order to meet its approximation guar- antee. Later Chen et al. (2017), Wilder (2018), and Anari et al. (2019) also gave bi-criteria approximation algorithms.
2. Related Work
Nemhauser et al. (1978) showed that the greedy algorithm achieves (1 -appo-aaproiinnaooonnn for cardinalitycoonsrranedd monotone submodular maximization. This is tight, unless P=NP (Feige, 1998). More algorithms for this and re- lated settings exist (Calinescu et al., 201 Badanidiyuru & Vondrák, 2014; Mirzasoleiman et al., 2015).
Instead of maximizing the minimum of multiple objectives, Soma & Yoshida (2017) considered regret ratio minimiza- tion where the goal is to find collection of subsets (rather than single subset) that approximate the Pareto optimal set to the multiple objectives. They designed algorithms for the problem which were improved by Feng & Qian (2021) and Wang et al. (2023). Malherbe & Scaman (2022) considered an objective based on quantile maximization. Recently, Wang et al. (2024) introduced the problem of maximizing the average of objectives subject to multiple constraints ensuring the value of each objective. Fazzone et al. (2024) studied more general problem and extended the algorithm of Krause et al. (2008) to obtain a sequence of approximately Pareto optimal solutions.
Krause et al. (2008) introduced the multiobjective submod- ular maximization problem in the context of robust exper- imental design. They provided bi-criteria algorithm and showed that the problem becomes inapproximable in the regime where B < k. Chen et al. (2017) also proved that computing (1 - )) approximate solution for the problem is NP-hard. When surveying approximation algorithms for the problem, we distinguish between two types of algorithms.
The first type uses a continuous relaxation of the submod- ular set functions/ f: 2 + E. F: [0, 10 + R, which is called the multilinear extension. After obtaining a con- tinuous solution via techniques from convex optimization, the solution is then rounded to output a single set. Such approaches have the benefit that they (almost) offer the best possible approximation ratio of e. However, evaluat- ing the multilinear extension is costly and impractical for
Related to the multiobjective problem, submodular maxi- mization has also been studied with fairness and diversity considerations for the output subset. In this context, each element is associated with categorical attribute such as race or gender, and the output is required to ensure that
2

---

An Asympiotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
no particular attribute value is under- or over-represented. This problem has actively been studied in both the offline setting (Celis et al., 2018; El Halabi et al., 2024; Tang& & Yuan, 2023; Yuan & Tang, 2023) and the streaming set- ting (HI Halabi et al., 2020; 2023; Wang et al., 2021; Cui et al., 2024).
Algorithm 1: Greedy for Problem 3.1
Input: Monotone and submodular set functions
fe: 2 - Rgo for E C, budget B, and the
optimal value OPT
((0 0: for i = 1.2, ...,, ...,Be. do
Let z10) E Av be a solution to the problem:
3. Problem Definition
Find E Dv such that for all c C' holds
We now formally define the notion of submodularity and the problem we consider in this work. A set function on a finite universe V is a function f: 2 + R on all subsets of V. A set function f is said to be monotone if f(S) I f()) for all
Σ xofelv| s(1-1) | VEV
1 (OPT- - fc(s(i-1)): B
5
(1)
sets S T S V. For sets S C and T C V. we define the
Sample ylt) ~ x0);;
marginal gain of over S as f(T [ = ((SUT)- -
6
Update ski) + S 1) U fo(0);
I consists of a single element v, we simply write f(v S) instead of f((v} S). A set funetion is called submodular
return S(B)
if it has diminishing returns, i.e., for all sets S C TTS V
and elements v E V holds that
running time of our algorithm and in necessary condition on the budget B.
Maximization of submodular functions is well-understood We consider (multiplicative) approximation ratios, so we assume throughout that submodular functions are nonnega- tive.
Further Notation. We use OPT for the optimal solution OPT = arg max mineec fe( of the multiob- jective submodular maximization (Problem 3.1). Abusing notation, we also use OPT to denote the optimal value, i.e., we write OPT = mincec (OPT). Given a finite set X, we denote the set of probability distributions over X as the simplex Ax = {ar E [0, 1|x =Emex Te = 1}. We will use this to denote probability distributions over the set of colors Ag or the universe Av.
In our work, we are interested in a generalization of this objective where we consider multiple submodular functions over the same universe. The goal is find set that maxi- mizes all functions at the same time:
Problem 3.1 (Multiobjective Submodular Maximization). Let C be a finite set, which we refer to as the set of colors, and define :: = IC]. We are given a universe V and mono- tone and submodular set functions fe: 2 + Rzo for each E C, all on the same universe V. Given budget B, we are asked to find set S C V of size |S] S B maximizing the least value among all colors, which is minsec fS).
4. Our Algorithm
We sketch the central component of our algorithm for multi- objective submodular maximization (Problem 3.1) in Algo- rithm 1. Note that this is merely to illustrate and motivate our core ideas, and we also provide an implementable ver- sion as Algorithm 2. Before delving into the analysis of our approximation guarantee, we want to motivate our algo- rithm design. For now, we assume that we know the optimal value OPT; an assumption that we will later remove.
In our work, we are concerned with the case when the bud- get is large compared the number of colors, i.e., B 2 k, as this avoids the regime where the problem becomes inap- proximable (Krause et al., 2008). Submodular maximization (i.e., the special case of single color) is known to be NP- hard as it generalizes the maximum coverage problem. For the latter, no polynomial-time algorithm with an approxi- is known. At the same time, the greedy algorithm provably achieves this approximation ratio for any submodular function (Nemhauser et al., 1978). Multiobjective submodular maximization (i.e., the general case of multiple colors) is a harder problem, but we aim for (almost) the same approximation guarantec. As in the prior work, our goal is to design an algorithm that provably obtains an approximation ratio of 1 e with probability 1 5 for any pair of e, 5 O. Both values show up in the
mation ratio better than
As in the greedy paradigm, we construct a solution Sto) over 1 < i S B iterations and in each iteration, we identify a good element ((0) to add. For the case of sub- modular maximization (i.e., the special case of single color), using the element with maximum marginal gain e = arg max,ev f(v s(i-1) is sufficient to obtain the (1 - 1 is not necessarily required to add the element of maximum marginal gain. Indeed, adding any element V whose
è >approximation. However, the analysis reveals that it
3

---

An Asympiotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
marginal gain satisfies the inequality
Algorithm 2: LP Greedy with Independent Repetitions
f(u 15(-11) 2
1 B
(2)
Input: Monotone and submodular set functions
fe: 2 - Rzo for E C, budget B, failure
probability 8
is sufficient. Intuitively, adding an element with marginal gain that is high enough compared to the distance to op- timality is sufficient, and it is easy to show that e* also satisfies Inequality (2). Transferring this to the case of mul- tiple colors is not straightforward as there is not necessarily a single element that satisfies Inequality (2) simultaneously for all colors с E C. Instead, we show that we can satisfy (2) in expectation with probability distribution z(*) E Av which is exactly what we require for (1) in the description of Algorithm 1. As of now, it is unclear that such probability distribution exists, but show this in the following lemma:
Sbest + 0:
for t = 1, 2,.,,, ...., [log(2/0)] do
8:0) + 0;
for i = 1,2,.... ...; B do
Let x:()) E Av be a solution to LP(S(i-1)):
Sample w(() ~ x((1;
Update 5() + S(i 1) f
if
minsec (c(S( 2 mineec fc(Sbes) then
Shest +- SS(B)
return Shest-
Lemma 4.1. In each iteration of Algorithm I, there is a solution 210) Dy that satisfies Inequality (1).
Proof. Fix an iteration i B. Let x' E [0. 1 be
the contrary, we are able to avoid continuous solutions as we discretize immediately by sampling a random element o(0)) V according to (0()) and adding it to our solution. The technical part of our analysis is concerned with showing that this leads to solution of high value for all colors E C, with sufficiently high probability. However, intuitively this is clear: Assume we have constructed a partial solution 5t)) that has low value for a specific color e E C. This means that the gap to optimality OPT f(((()))) larger for e than for other colors, so the solution (i-1) E Ay will put more mass on elements u V that satisfy (1) for the color c. This makes it more likely that fc(S()) will be larger, and overall that all colors have high value, given that the budget is sufficiently large.
such that a. = B if OPT and ot = 0 otherwise. Note that x" satisfies Inequality (1) for all e C' since
Σ xffe(o (8(11)) VEV
Σ
fo(v| 1 s(i-)))
B VEOPT
2 B fc(OPT | ((1-1))
(submodularity)
IV 2
- (F((PTT-f((S(-))) 1))
(monotonicity)
B (OPT- - -f((S(-1))
Even though we know that a solution (0 exists in each iteration, we still need to argue that we can find it efficiently. To this end, we rewrite the problem of finding (0)) satisfying Inequality (1) as an
Finally, we need to amplify the success probability of our algorithm, which we do via independent repetitions of Al- gorithm I. We detail our complete approach in Algorithm 2, which also no longer requires knowledge of OPT.
LP. Introducing an objective into the LP even allows us to remove the dependence on OPT:
Adding random elements has been considered in prior works on submodular maximization such as in the algorithm of Buchbinder et al. (2014) for non-monotone submodular maximization, where the randomness helps to avoiding bad elements. However, our algorithm and sampling carefully designed to solve the multiobjective problem: We choose our sampling probabilities to enforce progress across all colors simultaneously, which can be understood as discrete version of the continuous approach of Chekuri et al. (2010).
LP(S(i-1)): 1): max. &
(3)
s.t. Ve C: Σ
Fv (Bccv (( 26,
vEV
Σ F 1,
VEV
Ve E V: x. 2 0.
Note that the equivalence with (1) follows immediately by rearranging terms in the first constraint using the second constraint Evev Vx, = 1 and replacing with OPT. It is thus guaranteed by Lemma 4.1 that the optimal value e of the LP satisfies 5* 2 OPT.
4.1. Analysis Outline
We now state the approximation guarantee of Algorithm 1. This guarantee only holds if the optimal value OPT is suffi- ciently large, but we will show in Section 4.2 how to convert this into a guarantce that depends on the ratio of the budget B and the number of colors k |C| via pre-processing
Now, operating over continuous solutions z00) is impracti- cal as it involves relaxing the submodular functions. On
4

---

An Asympiotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
step. To bound the running time and the number of function will show in Section 4.3
only constraint on Alice is that Σ E|x, [D)) 2 ps that is, the sum of the means of the probability distributions
evaluations of our algorithm, how to use MWU to solve the LP efficiently. We defer some of our proofs to Appendix A.
D DB must be at least μ. If = / Xi. then for any c > 0,
Theorem 4.2. If OPT 2
where the maxi-
22p
mum marginal gain is M = max.ec maX.ev fc(v (), then Algorithm outputs a solution S such that
Pr[X S (1-c)/} exp
2MM
min fo(S) 2 1 (1---c) cEC
We use this to argue for concentration around (the lower bound on) the expectation, which was (1 O)PT:
OPT
e
with probability at least 1 - 6.
Lemma 4.6. Let S be the output of Algorithm 1. For each c C, it holds that
To prove the theorem, we begin with the basic observation that in each iteration, we add an element to the solution that for each c E C' good in expectation.
Pr [L((S) S (1- OPT
20PT
exp
E
4Mc
Lemma 4.3. In each iteration i of Algorithm I and for each color c C,
where M = maxrev Sc(v 10).
([fc(v()) (0--))(s(-11)
1 B (OPT-S((S(-1))
Proof. Fix c C. In the context of Theorem 4.5, we use X; = =c((o()) 5(i-1) and the distribution Dj over values fo(((0) S(-11) where e(ر ~ z((), As such, M max.ec Mc is also the maximum marginal value. Note that the random process is exactly as in Algorithm 1: In each iteration, we select a (possibly adversarial) solution a0()) to (I) which determines the distribution D. remains to argue that Σ E[X; D.] 2 ş for μ = (1 - O)PP.. However, we have just shown this in Lemma 4.4:
In expectation, we recover the greedy guarantee:
Lemma 4.4. Algorithm outputs a solution S such that for each e C C,
[[fc 1 (1-2) OPT.
B E[X
B Σ
The problem is that this is only in expectation, but we have to satisfy for all colors e E C simultaneously. To this end, we show how to use concentration results for martingales.
Σ
Dj =E E
Sc(v()
=Effc(S(B))] (1- OPT p.
To motivate analysis further we explain how this gener- alizes an easier problem that is better understood: Imagine that in each iteration i, we obtain (6) = x= as defined in the proof of Lemma 4.1 as a solution to (1). Since this so- lution does not change over the iterations, our algorithm is equivalent to throwing B balls (one ball per iteration) into B bins (one bin per element of OPT). It is known that the resulting number of non-empty bins is In fact, we have shown stronger statement in Lemma 4.4, i.e. that this even holds for functions that are submodular over the non-empty bins. Our analysis thus takes inspiration from concentration results for this balls-into-bin bins problem to obtain concentration. In particular, we use a form of Azuma's 's inequality due to Kuszmaul & Qi (2021):
Applying Theorem 4.5 now yields
Pr(fc(S) S c)pl [1pl==1 exp ( E2
<cxp
2M
Noticing that (1 - - <) OPT < (1 - e) and we have the lemma.
1 > 2
in expectation.
With the concentration for each color in hand, we are now ready to prove Theorem 4.2:
Proof of Theorem 4.2. Recall that we defined the maximum gain as M max.ec M. max.ec max,ev fe(v 0). Assuming OPT 2 A log(2k), we have by Lemma 4.6
Theorem 4.5 (Corollary 16 in Kuszmaul Qi (2021)). Sup- pose that Alice constructs sequence of random variables X1, X1....,Xp with X; E [0, M). M > O, using the follow- ing iterative process. Once the outcomes of XI...., X are determined, Alice then selects the probability distribu- tion D, from which X; will be drawn; X, is then drawn from distribution D.. Alice is an adaptive adversary in that she can adapt Dj to the outcomes of X1...., X;-1- The
for each c C' that
Pr Ja(S) S (1 1- OPT
OPT
2OPT
1
S exp
<
4M
2k
5

---

An Asympiotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
and by union bound over the k (dependent) colors, we obtain that the result holds for all C. with probability
Theorem 4.8. Bf 108 log k then
2. We repeat the algorithm r [10] times and
-
min fo fc(TUŠ) 2 eEC
OPT
output the best solution. Since repetitions are independent, the probability that none of the [log(1/6) solutions is a
e
(1 - - a>-appoxximation is 2 S e log(1/5) = D
with probability at least 1 -.
4.2. Removing the Condition on OPT
Comparison with prior work. We compare our condi- tion B = Q log k) of Theorem 4.8 with conditions on the budget of prior work. Udwani (2018) requires that S 10 for an approximation ratio of 1
We can push the condition on OPT into a condition on the relation of the budget B to the number of colors k = =C', which we state in Theorem 4.8. As do all (1 - e)- e)- approximation algorithms for Problem 3.1, we also require the budget to be large. Recall that this avoids the regime where the problem becomes inapproximable (Krause et al., 2008) and is natural for many of the applications we men- tioned in the introduction. Our condition is slightly less restrictive compared to the prior work, and we provide a detailed comparison at the end of this section.
- - Te
log B B ) In order to achieve an approximation ratio of - 6, his algorithm requires that B = ( The algorithm of Tsang et al. (2019) provides a similar approxi- mation that is also dominated by the term B.3. Since they have to use the same choice of e, their algorithm has the same condition on B. The condition on c in both works requires _ 2 10 log k. which means that our condition for Theorem 4.8 is never more restrictive, while our condition is strictly less restrictive in its dependence on c.
The key is a pre-processing step where we climinate ele- ments E V whose value fe(v ()) is large compared to C, as such elements impair the
OPT for any color concentration. We find such elements and add them to a par- tial solution T'. Afterwards, some colors may have reached OPT. However, we now only consider the colors
4.3. MWU and Lazy Evaluations
Algorithm may still be impractical. First, solving the I.P may be expensive and second, we need to evaluate all marginal gains in each iteration. The latter is also problem appearing in the greedy algorithm for a single color and we there resort to lazy evaluations. It turns out that we can solve both efficiency problems via multiplicative weights updates (MWU) (Arora et al., 2012). In particular, we show that solving the LP approximately via a few rounds of MWU is sufficient, and we even transfer lazy evaluations to multiple colors. We note that MWU have been used in the context of multiobjective submodular maximization, but solve a continuous relaxation of the problem (Chekuri et al., 2015).
Ö fc E C: fc(T)= < ОPT}
fc
which have not yet reached OPT. Our pre-processing guar- antees that marginal gains for colors e E C on top of the partial solution T are small compared thus not problematic for Algorithm 2. This is similar to the pre-processing step described by Udwani (2018), but our pre-processing does not require knowledge of OPT. We defer the full description of the pre-processing routine to Algorithm in Appendix A.2, along with all proofs.
OPT, and are
We detail this in Algorithm 4 in Appendix A.3. We cru- cially use that solving LP(S) admits a formulation as a two-player game: The first player selects a probability dis- tribution y E Ag over the colors, and the second player responds with the element v E V which maximizes the convex combination Ecec Vele(v) where le(v) is loss (or rather, a gain) given as Lo(v) Finding the best response thus entails a search over all ele- ments E V, and we show how to transfer the concept of lazy evaluations to the multiobjective problem in order to reduce the number of function evaluations practice. Fur- thermore, two-player games can be solved efficiently using few rounds of MWUs (Arora et al., 2012). The complication is to bound the number of rounds, and we do so by appealing to the structure of our problem. This allows us to bound the overall running time of our algorithm. Note that we first run the pre- prepprocsssing described in Algorithm 3, and then apply Algorithm 2 where we solve the LP approximately using MWU as described in Algorithm 4.
We then run Algorithm 2 with reduced budget B B- on functions fa(AA- fa(A U T), which ensures by sub- modularity that marginal gains are small for the modified instance. The technical difficulty is to show that reducing the budget does not result in a big decrease of the optimum, which is non-trivial for multiple objectives. We provide the following novel result:
Bf((v S) + fo).
Lemma 4.7. Let OPT, = maxsçV: Sigb min CEc fc(S) for b 2 O. Let > 0 be such that fe(u | 0) S 7OPT for all E V and e E Ò. Then, for B < B.
B log k
B
ÖPT B 2
1- 11 37
37-
HOPT.
B
Note that prior work uses similar results but over the contin- uous space, which makes our result more challenging. Let Š be the solution of Algorithm 2 to the modified instance. We have the following guarantee on the combined solution:
6

---

An Asympiotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
Theorem 4.9. Our algorithm for multiobjective submodu- lar maximization runs in time (n 2 log(k) (18(1/8) and requires OKnBk log(1/8)) function evaluations.
In many real-world networks, nodes are not uniform but var- ied in terms of attributes. Examples include social networks, where nodes have sensitive attributes such as race, gender, religion, or even political opinions. Suppose that we have a network in which each node has a categorical attribute such as race or gender. Centrality maximization without any consideration of the variation of node attributes may lead to undesirable outcomes. Indeed, as the objective function, i.e., the centrality measure employed, does not take into ac- count the variation of node attributes, it cannot distinguish between parts of centrality scores of the target node corre- sponding to nodes with different attribute values. Therefore, even if the centrality score of the target node is maximized, the node might still not be sufficiently visible to nodes with some specific attribute value. This is problematic, for in- stance, in the case where we use centrality maximization to improve the visibility of public health agency's 's accounts in social media platform. Such accounts should be sufficiently visible even to minority users.
We also defer this proof to Appendix A.3. We compare this with the (1 - _ appppooximtaio algorithm of Ud- wani (2018), which has a similar condition on B but needs (ken)) function evaluations. The faster ((1 - 5)² c)- approximation algorithm requires ( function eval- uations by repeatedly solving submodular maximization problems using a nearly-linear time algorithm developed by Mirzasoleiman et al. (2015). Furthermore, the (1 - é e)- approximation algorithm of Tsang et al. (2019) needs Ó + 8+) evaluations of the multilinear extension and its gradient, and needs O ( + kBa + _²)) additional time. Note that the evaluation of the multilinear extension is generally not tractable and usually estimated via sam- pling (Salem et al., 2024). Only special structure of the submodular functions allows for more efficient evaluations.
We therefore study centrality maximization with fairness considerations, taking into account the variation of node attributes. To this end, we introduce a novel centrality measure, which we refer to as the fair harmonic central- ity. This measure is generalization of the aforementioned harmonic centrality, which contributes to finding a fair so- lution in terms of node attributes. Let now C' be a set of colors, i.c., attribute values. Let é: V + C' be a mapping that assigns each node to a color. For each e E C, define Ve = {v E V l(v) = c). We define the fair harmonic cen- trality based the maximin fairness (Rahmattalabi et al., 2019) as follows:
5. Fair Centrality Maximization
We now introduce our novel application which furthers the applicability of algorithms for multiobjective submodular maximization. Centrality measures, quantifying the impor- tance of nodes or edges in a network, play a key role in network analysis (Das et al., 2018). In many real-world see- narios, we want to optimize the centrality score of a target node by intervening in the structure of the network (e.g.. by adding removing edges around the node). In particular, centrality maximization is well-studied task, where given a directed graph G = (V, A), a target node E V, and budget B E Σo. we are asked to insert at most B edges heading to v that maximize the centrality score of v (see e.g., (Bergamini et al., 2018; Crescenzi et al., 2016; Angelo et al., 2019; Ishakian et al., 2012; Medya et al., 2018)).
min (v) = min
Σ uEVA(t
(4)
cEC IVe \ {nHl
d)(u,o)
This represents the minimum value among all parts of the harmonic centrality score of corresponding to nodes with different colors, normalized by their populations. Clearly, the above is a generalization of the original harmonic cen- trality. Based on this measure, we formulate:
Among existing centrality measures, the harmonic centrality is one of the most well-established (Boldi & Vigna, 2014). The harmonic centrality score of e E V is defined as
hG(v)= =
Σ
1
Problem 5.1 (Fair Centrality Maximization). Given di- rected graph G = (V, A). mapping é: V + C, target node v E V, and budget B E Z>o, we are asked to find F C {u E V (u, v) $ A) x {0) with |F| < B that maximizes hminn ((VAUP) (v).
(MV dd(u,v) v)
where du(u, v) is the shortest-path distance from u to v on G. Intuitively, the score quantifies the importance of nodes based on the level of reachability from the other nodes. Boldi& & Vigna (2014) showed that unlike previously known centrality measures, the harmonic centrality satisfies all the desirable axioms, namely the size axiom, density iom, and score monotonicity axiom. Recently, Murai & Yoshida (2019) theoretically and empirically demonstrated that among well-known centrality measures, the harmonic centrality is most stable and thus reliable against the struc- tural uncertainty of networks.
This is a special case of the multiobjective submodular max- imization (Problem 3.1), since every term in the minimum in (4) is submodular in F. as in the original harmonic cen- trality (Crescenzi et al., 2016). Existing algorithms for mul- tiobjective submodular maximization either offer weak theo- retical guarantees or rely on the multilinear extension of the objective function; however, the evaluating the latter is com- putationally expensive when considering our fair centrality
7

---

An Asympiotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
maximization problem for large-scale networks. With our al- gorithm, we the first to solve multiobjective submodular maximization on this scale with the strongest guarantee.
LP Gready Groedy Minimum
Groedy Round Robin Saturato
Udwani MWU
Value sain, 1.18)
0000
6. Experimental Evaluation
#Function
4000
10
2000
We evaluate our algorithm, natural greedy baselines, and other prior work on synthetic and real-world instances for max-k-cover, fair centrality maximization, and fair influence maximization. We run our experiments in Python on ThinkPad X1 Carbon with an Intel Core i7-1165G7 CPU and 16GB of RAM. Our code is publicly available.'
10
90
Budget
Budget
Figure 1. Multiobjective submodular maximization for max-k- cover. We use = 20 Kronecker graphs on n = 64 nodes. We show the function value (left) and the number of evaluations (right), We report mean and standard deviation over 5 random instances.
6.1. Al Algorithms
We use our algorithm and several baseline algorithms with and without theoretical guarantees. For baselines that re- quire an estimate OPT' to the optimal value, we use an outer loop that performs a binary search for OPT', Note that our algorithm does not require such an estimate.
Saturate. We use the bi-criteria algorithm SATURATE due to Krause et al. (2008) heuristic with fixed bud- get. The algorithm uses a guess OPT' to the optimal value and optimizes greedily over the submodular function fsatuRaTe (S) = Ecec (S), OPT').
LP Greedy. We use our Algorithm 2 with 20 repetitions of the outer loop to boost the success probability, and solve IP (3) using Gurobi Optimizer 11 1 (Gurobi Optimization, LLC, 2024). We facilitate lazy evaluations differently from the MWU described in Algorithm 4: In each iteration i, we solve I.((S(-1)), but using the upper bounds (e(v)) in place of the real marginal gains. Whenever the solution x E Av to the LP places mass Tep 0 on an element V V. we evaluate and update ge(v)= = fe ((-))). We then solve the LP again and repeat this until the real marginal gains of all elements v E V with v, > O are evaluated. We omit the pre-processing described in Algorithm 3. Algorithm 2 may act overly conservative in its selection to preserve the approximation ratio for difficult instances. We thus modify the left-hand-side of the first constraint of LP (3) to be
Udwani's MWU. We use the efficient (1 - 4)²- approximation described by Udwani (2018) (UDWANI MWU). We follow his implementation details and also omit the pre-processing. We use 100 iterations with step size of r = 0.1 OPT' We use the lazy greedy implementation to solve the inner maximization problem.
Continuous Frank-Wolfe for influence maximization. We use the algorithm of T Tsang et al. (2019) and their imple- mentation. The algorithm relies on the fast evaluation of the multilinear extension for fair influence maximization, and thus we use it only for fair influence maximization.
6.2. Max-ks-Cover
First, we replicate the setup of Udwani (2018) for max- k-cover instances: Here, we generate k random synthetic graphs {Ge (V, Fee) on fixed vertex set V. The
Σ VEV
(BJa(v) (((-1))+ + +
cover size of U C V on graph Ge is fo(U) = [NN. where NG. (U) = (fu, E E. : u E U or U E U}. We use h = 20 stochastic Kronecker graphs on n = 64 nodes which reflect real-world networks and are detailed in Ud- wani (2018) and Leskovec al. (2010). Our results are in Figure and we include further experiments other graphs in Appendix B.1. This shows that we achieve the highest objective with fewer function evaluations than other algo- rithms, particularly compared with UDWANI MWU which is the only other algorithm with theoretical guarantees.
where o >> 1 is factor that controls the greediness of our algorithm: For larger Φi our algorithm prefers to increase the color that currently has the least value, instcad of picking a distribution r that leads to a balanced increase. Throughout, we use a factor ø 10. We include an ablation study for the number of repetitions of the outer loop and the factor Øb.
Greedy heuristics. We use two greedy heuristics. First, we use the heuristic described by Udwani (2018) (GREEDY ROUND ROBIN): In < < B iterations, we add one element after another to the solution Sti-1), We select the i-th element as v,() = arg max,ev fe- | 5()-1) where c² = i mod k. We use another greedy heuristic (GREEDY MINIMUM), where c' arg min.ec 1)(
6.3. Fair Centrality Maximization
We use Amazon co- co-purchasing networks used by Anagnos- topoulos et al. (2020) and Miyauchi et al. (2023) along with the color attributes which represent product categories to ob-
httpp:://gi thub. wwt.cccmm///// 22m7m228144 4/14/mml/ cicbbeeeetttt
8

---

An Asympiotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
LP Groody Greedy Minimum
Groady Round Robin Saturate
Udiaari MMU
Greedy
Saturate
43-
0.55
#Funciin evaluations
10P
-2-
Value (..5)
0.50
0.45
1.0
0.00
39
10
10
20
100
200
100
200
500
Number of repetition
Gready factor
Burlger
Budget
Figure 4. We run Algorithm 2 on a max-k instance of 20 Erdös-Rényi random graphs
Figure 2. Fair centrality maximization the Amazon purchasing graph Arts, Crafts & Sewing with n = 5051 nodes and k 2 colors.
64 nodes with p 0.1. For the left plot, we vary the number of repetitions while using é 10. For the right plot, vary the factor ó while using 20 repetitions. We report mean and standard deviation over 5 runs.
LP Gready Gready Minimum
Greedy Round Rabin Trang et al. PW
Saturate
0.3
especially for large budgets. We omit UDWANI MWU as it exceeds 10 minutes per run. The algorithm of Tsang et al. (2019) uses special evaluation oracles for the gradient of the influence which do not correspond to function evaluations, so we report the running time instead. Recall that their algo- rithm is specialized to influence maximization, for which we can evaluate the multilinear extension efficiently. Our algo- rithm applies to any multiobjective instance. Appendix B.3 contains results for further attributes, which includes one instance where the heuristic SATURATE outperforms our algorithm for small budget. Results for the remaining graphs in Tsang et al. (2019) are similar, so we omit them.
Volue [45)
Turning time [s]
100
100
0.1-
00-
10
20
30
40
50
30
20
30
00
Burgee
Busiget F
Figure 3. Fair influence maximization on a simulated Antelope
Valley network of n= 500 nodes on attribute ethnicity with k =5
tain instances for our fair centrality maximization problem as defined in Section 5. The networks are available online (tsourakakis-lab, 2024) and contain large graphs of up to 10 380 nodes and 53 680 edges. We select an arbitrary target node among the nodes with median degree. Figure shows results for a single network called Arts, Crafts & Sewing and we include results for other networks in Appendix B.2. Throughout, our algorithm achieves the highest objective value with fewer function evaluations than UDWANI MWU and SATURATE, which are the strongest competitors. This is mainly because, compared to these two algorithmss, our method does not require a binary search to determine good guess the optimal value.
6.5. Ablation Study
Figure 4 provides an ablation study for the number of rep- etitions and the factor é which makes the algorithm act less conservatively. We use simple synthetic instance of Erdös-Rényi random graphs for the max-k-cover problem. Our results show that after 20 repetitions, our algorithm has surpassed the objective value of SATURATE and more rep- etitions do only contribute to a slight increase in objective value. The right plot shows that a factor of approximately & E [5, 15) results in the highest objective value.
7. Conclusion
6.4. Fair Influence Maximization
We introduce the first scalable algorithm for multiobjec- tive submodular maximization that achieves a (1 - e)- approximation ratio. Going beyond fair centrality maxi- mization and influence maximization, many problems in faireess naturally admit formulations as multiobjective prob- lems. The high scalability and theoretical guarantees of our algorithm make well-suited option to address such prob- lems. Further, we avoided the common methodology of op- timizing in the continuous space and rounding the resulting solution. Our novel techniques may lead to improvements in areas even beyond the multiobjective problem.
Finally, we replicate the setup of Tsang et al. (2019) for their influence maximization objective, where the diffu- sion follows the independent cascade model (Kempe al., 2003). They define instance for multiobjective sub- modular maximization via the colored influence fc(S)=
V. E[number of nodes with color e that S' activates]. We
use their simulated Antelope Valley networks n 500 nodes which can be colored according to different node attributes. As in Tsang et al. (2019), we use 000 samples to approximate the influence. Figure shows results for the attribute ethnicity, where we outperform the prior work

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
Impact Statement
Chekuri, C., Vondrák, J., and Zenklusen, R. Dependent randomized rounding via exchange properties of com- binatorial structures. In Proceedings of FOCS '10, pp. 575-584, 2010.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Chekuri, C., Jayram, T. S., and Vondrák, On multiplica- tive weight updates for concave and submodular function maximization. In ITCS, pp. 201-210. ACM, 2015.
References
Anagnostopoulos, A., Becchetti, L., Fazzone, A., Menghini, C., and Schwiegelshohn, C. Spectral relaxations and fair densest subgraphs. In Proceedings of CIKM '20, pp. 35-44, 2020.
Chen, R. S., Lucier, B., Singer, Y., and Syrgkanis, V. Robust optimization for non-convex objectives. In Proceedings of NeurlPS '17, pp. 4705-4714, 2017.
Chen, Y. and Kuhnle, A. Practical and parallelizable al- gorithms for non non-monotone submodular maximization with size constraint. Journal of Artificial Intelligence 2024.
Anari, N., Haghtalab, N., Naor, S., Pokutta, S., Singh, M., and Torrico, A. Structured robust submodular maximiza- tion: Offline and online algorithms. In Proceedings of AISTATS '19, pp. 1128-3137, 2019.
Research,
Crescenzi, P., D' Angelo, G., Severini, L., and Velaj, Y. Greedily improving our own closeness centrality in network. ACM Transactions on Knowledge Discovery from Data, 11(1):1-3,, 2016.
Arora, S., Hazan, E.. and Kale, S. The multiplicative weights update method: A meta-algorithm and appli- cations. Theory of Computing, 8(1):221-664 2012.
Badanidiyuru, A. and Vondrák, J. Fast algorithms for maximizing submodular functions. In Proceedings of
Cui, S., Han, K., Tang, S., Li, F., and Luo, Fairness in streaming submodular maximization subject to knap- sack constraint. In Proceedings of KDD) '24, pp- 514-525, 2024.
SODA 14. pp. 1497-1514, 2014.
Bai, W. Noble, W. S., and Bilmes, J. A. Submodular maxi- mization via gradient ascent: The case of deep submodu- lar functions. In NeurlPS, pp. 7989-7999, 2018.
Angelo, G., Olsen, M., and Severini, L. Coverage central- ity maximization in undirected networks. In Proceedings of AAAI '19, pp. 501-508, 2019.
Bergamini, E., Crescenzi, P., D' Angelo, G., Meyerhenke, H., Severini, L.,, and Velaj, Y. Improving the betweenness centrality of a node by adding links. ACM Journal of Experimental Algorithmics, 23:1-32, 2018.
Das, K., Samanta, S., and Pal, M. Study on centrality measures in social networks: A survey, Social Network Analysis and Mining, 8:1-11,0015
Bilmes, J. A. Submodularity in machine learning and ar- tificial intelligence. arXiv preprint arXiv:2202.00132, 2022.
El Halabi, M., Mitrović, S., Norouzi-Fard, A., Tardos, J., and Tarnawski, J. M. Fairness in streaming submodular maximization: Algorithms and hardness. In Proceedings of NeurlPS 200 pp. 13609-13622, 2020.
Boldi, P. and Vigna, S. Axioms for centrality. Internet Mathematics, 10(3-4):222-266 2014.
El Halabi, M., Fusco, F., Norouzii-Frdd, A., Tardos, J., and Tarnawsi,, J. Fairness in streaming submodular maxi- mization over a matroid constraint. In Proceedings of ICML 23, pp. 9150-9171, 2023.
Buchbinder, N. and Feldman, M. Extending the extension: Deterministic algorithm for mon-monotone submodular maximization. CoRR, abs/2409. 2024.
Buchbinder, N., Feldman, M., Naor, J., and Schwartz, R. Submodular maximization with cardinality constraints. In Proceedings of SODA '14, pp. 1433-1452, 2014.
El Halabi, M., Tamawski, J., Norouzi-Fard A., and Vuong, T.-D. Fairness in submodular maximization over troid constraint. In Proceedings of AISTATS '24, pp. 1027-1035, 2024.
Calinescu, G., Chekuri, C., Pál. M., and Vondrák, J. Max- imizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6); 1740-1766, 2011.
Fazzone, A., Wang, Y., and Bonchi, Fair representation in submodular subset selection: A Pareto optimization approach. Transactions on Machine Learning Research, 2024.
Celis, L. E., Huang, L., and Vishnoi, N. K. Multiwinner vot- ing with fairness constraints. In Proceedings of IJCAI '18, pp. 144-151, 2018.
Feige, U. threshold of Inn for approximating set cover. Journal of the ACM, 45(4):63446)) 652, 1998.
10

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
Feng, C. and Qian, C. Multi-objective submodular max- imization by regret ratio minimization with theoretical guarantee. In Proceedings of AAAI '21, pp. 12302-12310, 2021.
Murai, S. and Yoshida, Y. Sensitivity analysis of centralities unweighted networks. In Proceedings of The Web Conference '19, pp. 1332-1342, 2019.
Nemhauser, G. L. and Wolsey, L. A. Best algorithms for approximating the maximum of submodular set func- tion. Mathematics of Operations Research, 3(3):177-188, 1978.
Fujishige, S. Submodular Functions and Optimization, vol- ume 58 of Annals Discrete Mathematics. Elsevier, 2005.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https: www. gurobi. com.
Nemhauser, G. L.. Wolsey, A., and Fisher, M. L. An analysis of approximations for maximizing submodular set functions Mathematical Programming, 14:265- 294, 1978.
Ishakian, V., Erdös, D., Terzi, E., and Bestavros, A. A framework for the evaluation and management of network centrality. In Proceedings of SDM '12, pp. 427-438, 2012.
Orlin, J. B., Schulz, A. S., and Udwani, R. Robust mono- tone submodular function maximization. Mathematical Programming, 172:505-537, 2018.
Kempe, D., Kleinberg, J., and Tardos, É. Maximizing the spread of influence through social network. In Proceed- ings of KDD '03, pp. 137-146, 2003.
Rahmattalabi, A., Vayanos, P., Fulginiti, A., Rice, E., Wilder, B., Yadav, A., and Tambe, M. Exploring al- gorithmic fairness in robust graph covering problems. In Proceedings of NeurIPS '19, pp. 15750-15761. 2019.
Krause, A. and Guestrin, Near-optimal observation se- lection using submodular functions. In Proceedings of AAAI '07, pp. 1650-1654, 2007.
Salem, T. S., Özcan, G., Nikolaou, I,, Terzi, E., and loan- nidis, S. Online submodular maximization via online convex optimization. In Proceedings of AAAI '24, pp. 55038-15046, 2024.
Krause, A., McMahan, H. B., Guestrin, C., and Gupta, A. Robust submodular observation selection. Journal of Machine Learning Research, 9(22)2761-280) 2008
Kuszmaul, W. and Qi, Q. The multiplicative version of Azuma's inequality, with an application to contention analysis. arXiv preprint arXiv:2 00200007....00.. 2021.
Soma, and Yoshida, Y. Regret ratio minimization in multi-objective submodular function maximization. In Proceedings of AAAI '17, pp. 905-911, 2017
Leskovec, J., Chakrabarti, D., Kleinberg, J. M., Faloutsos, C., and Ghahramani, Z. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research, 11333)985-1102, 2010.
Tang, S. and Yuan, J. Beyond submodularity: A unified framework of randomized set selection with group fair- ness constraints. Journal of Combinatorial Optimization, 45(4):102, 2023.
Malherbe, C. and Scaman, K. Robustness in multi-objective submodular optimization: A quantile approach. Pro- ceedings of ICML '22 pp. 14871-14888 2022.
Tsang, A., Wilder, B., Rice, E., Tambe, M., and Zick, Y. Group-fairness in influence maximization. In Proceed- ings of IJCAI '19, pp. 5997-6005, 2019.
Medya, S., Silva, A., Singh, A., Basu, P., and Swami, A. Group centrality maximization via network design. In Proceedings of SDM 18, pp. 136-134,20 2018.
tsourakakis-lab.
Github:
Densest di-
verse subgraphs, 2024. / //github htt..//oo//soraaais-eeeeee sineettt-divveee--uuuuue
URL
https:
Minoux. M. Accelerated greedy algorithms for maximizing submodular set functions. In Proceedings of the 8th IFIP Conference on Optimization Techniques, pp. 234-243, 2005.
Udwani, R. Multi-objective maximization of monotone
submodular functions with cardinality constraint. In Pro- ceedings NeurIPS '18, pp. 9513-9524, 2018.
Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondrák, J., and Krause, A. Lazier than lazy greedy. Proceedings of AAAI '1, pp. 1812-1818, 2015.
Neumann, J. Zur theorie der gesellschaftsspieke Mathe- matische Annalen, 100(1):295-320, 1928.
Miyauchi, A., Chen, T., Sotiropoulos, K., and Tsourakakis, C. E. Densest diverse subgraphs: How to plan a suc- cessful cocktail party with diversity. In Proceedings of KDD 233 pp. 1710-1721, 2023.
Wang. Y., Fabbri, F., and Mathioudakis, M. Fair and rep- resentative subset selection from data streams. In Pro- ceedings of The Web Conference '21, pp. 1340-1350, 2021.

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
Wang, Y., Zheng, J., and Meng, F. Improved algorithm for regret ratio minimization in multi-objeccive submodular maximization. In Proceedings of AAAI 22, pp. 12500- 12508, 2023.
Wang, Y., Li, Y., Bonchi, F., and Wang, Balancing utility and fairness in submodular maximization. In Proceedings of EDBT 24, pp. 1-14, 2024.
Wilder, Equilibrium computation and robust optimiza- tion in zero sum games with submodular structure. In Proceedings of AAAI '18, pp. 1274-1281, 2018.
Yuan, J. and Tang, S. Group fairness in non-monotone submodular maximization. Journal of Combinatorial Optimization, 45(3):88, 2023.
12

---

An Asympiotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
A. Omitted Details and Proofs
A.I. Missing Proofs from Section 4.1
Lemma 4.3. In each iteration i of Algorithm and for each color c. E C,
1 E[fa(u()) 1 1((11) (ttii1 z B (f((-
Proof. This follows directly by our algorithm design and the definition of expectation:
E(fc(v()) (((=)) | 1(i-1))
Σ
Pr(v = = 8 Sit | ((
NEV
Σ
1 fe(v (((-11
"EV
(OPT 1c(S(1-1))
Lemma 4.4. Algorithm/ 1 outputs solution S such that for each e C,
[[fa(s)] 2 (1- OPT.
Proof. We do the unrolling in the standard greedy analysis, but in expectation over the result of Lemma 4.3. That is, Lemma 4.3 is equivalent to
E(f((S())- - OPT + OPT |
|s(-11)
B (OPT- - -c(sti-))))
EOPT (c((()) |5(1-)] 1 (1- ) (OPT-5(s6--1))
Now, unrolling this yields
EOOPT - [c(S(B))] = Eg(a-1)
| - -PPT- (c(((())) s(l-a)s
1
Es(s-1)
OPT - fc(S(B-11)]
B
< ...
1
B
OPT
B
OPT,
which is equivalent to ([(f(S(()) 2 (1 ! OPT.
A.2. Details about Removing the Condition on OPT
Before going into the analysis of Algorithm we want to again motivate our algorithm design. Instances can violate the condition OPT 2 M log(2k) only in two ways. First, if the budget is small, it may happen that the optimum solution is not much larger than M. For instance, in the extreme case in which B = 1, we also have OPT M and necessarily violate the condition for OPT. Second, even if we have a large budget, the optimum solution value may still not be much larger than M due to submodularity, even for a single color. However, we will show that the latter case is not an issue, and we only require a sufficiently large budget. This rests on the fact that cases in which M is large compared to OPT, there are only few elements with large marginal gain. We can find those elements pre-processing step and add them to our solution
13

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
Algorithm 3: Pre-Processing for Algorithm
Input: Monotone and submodular set functions fe: 2 IR for E C' and per-color budget 1²'
T 75400 0;
for C C do
for i 1,2,...... ,,,,...,,'" B' do
Let = arg v fo(v T); Update TU {
return T.
before running Algorithm& 2. The remaining elements can only have low marginal gain, which then allows us to obtain better concentration.
Recall that == =cE fc(T) < OPT} where the output of Algorithm 3. Recall also that we define a modified instance where f( for all E Ć and A S V.
Lemma A.1. Algorithm 3 outputs set T of size (T) < kB'. Furthermore, fe(v () s
OPT
for all e E Ò and E V. B"
Proof. By the definition of Algorithm 3, we add at most B' elements per color, meaning the set T has size at most kB'. To show the second claim, let now E C and
be any element. If E T then fe ()) fc(u T) 0 and we are done. We may thus assume that did not add to T. For the proof, let for color c, and let ( denote Te at the end of iteration Since we did not add to Te, the greedy selection implies that fe(v T) S fe(v ((-1)) S fa(u(() (() for all < Sish B'. Hence,
denote with T. the elements that added to T
fa T)
Σ fa(v()) ((i-1)) ( (10)) S B Sc(T) S OPT
where the penultimate inequality is by submodularity, and the last inequality due to c Č.
In the end, effectively reduce the maximum singleton marginal gain which is sufficient improve the concentration in Theorem 4.2. However, Algorithm now runs with reduced budget B < B. We thus need to show that even with a reduced budget, we can still get a good fraction of OPT as long as B is sufficiently large.
show that T U attains good fraction of the optimum solution. Clearly, Lemma A.I shows that
Lemma 4.7. Let OPT, = max majsssv min Jc(S) for b 2 0. Let γ > O be such that felv 0) < >OPT for all E V and Ò. Then, for B < B,
B log k
B
OPT 2
1
3
OPT
B
B
Proof. We use probabilistic argument. As before, we abuse notation and use OPT, to denote both the optimum solution and its value. Let x- E {0, 1)V be such that 2 1 iff ÖPTв B and x; otherwise. We define ă (1 B) )x e [0, 1] as similar vector but with a reduced budget. Let F.: [o, 1j + R be the multilinear extension of f. for each E č. Since xx" {0, 13 have (OPTB) Fo(xx). As argued in Lemma of Udwani's work (Udwani, 2018), we have
B B F - fc -
F. (
which is due to Jensen's 's inequality and since the multilinear extension is concave in positive direction. We now use swap rounding (Chekuri et al., 2010) to obtain set C V from ă size |$| = B. Importantly, swap rounding is an oblivious rounding scheme, meaning it does not evaluate fc. such, we do not create rounded solution specific for but the
14

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
guarantee the rounded solution holds for all C. We have the following guarantee (Chekuri al., 2010) for rounded solution S, for all 8
0,
Fc())8²
8²B
Pr(f.(5) s -1- -)) & exp
S exp
Sexp
(6)
2M
2BTOPT
2
For the second incquality, we used that Me = max,ev fo(v 0) S OOPTB and Inequality (5). For the last inequality,
we used that (cPPPT 2 OPTB B. We need that the RHS of Inequality (6) is less than 1/k to guarantee that the rounded solution exceeds (a) for all E C. In particular, we choose
8 2yB
8 = 37 logk = exp
<
B
k
By a union bound over all E C.C.
Pr there exists ace E with fc(5) s (1 - F))((t) k =1
k
As such, the event that $ obtains value fc(5) 2 (1 (1--8) ()) for all c E simultancously has non-zero probability, meaning that such set S exists. Let S now be this set. We have for all E C that
B
OPT B 2 f(()) 2 (1 Ft) 2 (1 - 8) OPT
run the pre-processing Algorithm for a value B >> 0 which we will specify later Theorem 4.8. This outputs a set of
colors Ö C C and partial solution T S V, and we run Algorithm 2 use objective functions defined as fc(A) = (U for C' and the budget B B [T'. Since for E C. C have already reached the optimum value, simply ignore those colors and do not pass them to Algorithm 2. Algorithm outputs set S S V and the final solution of the combined algorithm is T S.
We can now put everything together to get the guarantee on the combined algorithm that only requires a large budget.
Theorem 4.8. If B 2 108 & & log l then
min US( 2 1- (1---c - OPT aEC
with probability at least 1 -
Proof. We use B + where y 36 log for Algorithm 3 which yields a partial solution T' and colors Ö C C. We show the theorem statement for all c C separately. If c of Č, we have by monotonicity that
2
fa fT) OPT.
Let now Ö. After the pre- pre-processing, we have by Lemma A.1 that [T| S so Lemma 4.7,
B
B
T
B and hence, by
1 k. (--b)
(1-1
(1-
OPT a 2 OPT
37 x
log k
(7)
By
Now, since B
3k by
get By
well
1
1
22
37
log k < 37
log k < 47 log k
1
9
By
15

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
Algorithm 4: Solving the LP with MWU and Lazy Evaluations
Input: Monotone and submodular set functions fe: 2 R for E C, partial solution S S V. upper bounds ge(v) for all v E V and E C such that ge(v) 2 fe(v S), step size r > 0, and number of iterations T
Initialize Ye +- C/ for all c E C' and Z t 0 for all v E V;
for 1, 1. do
Let v² f -; for v E V order decreasing in Eeec MoTa(v) do of * 1 and Eesc (ege(v) Leec VoTe(v*) then
break;
not yet computed, evaluate fe(u [S for all E C; Update (c(v)) t fe(e) 8) for all c E C; if o- =1 or EeEc MeBe(r) EeEc (V") then Set v* t;
Update Yo + (c n((((")) yc "BB(((v" (S) fa(S)));
Normalize V/ + yo/ 1
Add Fy- <- -y-- + :
14 return T and the updated upper bounds (e( for all and C.
which means bound (7) further and obtain
(1 (1-3() _ OPT
OPT B
(8)
3
Lemma A. I also says that after pre- pre-processing, the maximum singleton marginal gain
Me max fo 0) < 7OPT SOPTB S 2,PP 8
NEV
where the last inequality follows from (8). Hence, by Theorem 4.2,
fc(S) > 1 (1- -
OPT
with probability at least - 8. Let us condition on the case that Algorithm 2 was successful and (9) holds. this case, putting everything together yields
fc(TUš) = f5(
(definition of fe)
IV
OPT
(by (9))
e
3
W
OPT
B
(by (8))
1
1
OPT
6
OPT.
(monotonicity)
A.3. Missing Details and Proofs from Section 4.3
Let us now describe and motivate the design of Algorithm 4. Imagine a single iteration of Algorithm 1 where we have a partial solution 5 I( We can formulate the LP (3) as zero-sum game with a payoff for each element and each color E C defined as
(c(v) = Bf.(v S) + fc(S).
(10)
16

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
We write our LP in terms of this payoff:
Σ xxpfe()) WEV
Σ Vololu) GEC
LP(S) = max min zEAv CEC
min max yEdc DEV
where we able to exchange minimum and maximum this presents a zero-sum game (v. Neumann, 1928). We use the mix-max formulation where the first player plays a distribution Ac over colors and the second player responds with the best response
arg max eEV
Male(v) = arg IIX BEV
Σ CEC
MeSelv (S)
CEC
where the equality true since (S) constant u. Since the RHS just a linear combination of marginal gains, we employ lazy evaluations when finding the maximizer v²: While maintaining upper bounds ge(v) 2 Se(v () for all E V.c E C, it verify that EcEc fefo(e) S) > Eoec (ege(v). Since the solution S we build increases and marginal gains are decreasing due to submodularity, we use prior marginal gains for ge(v), and update the upper bounds until we can show optimality of v".
Finally, we understand the colors as experts and, treating {(o) = (Lo(U))OEc E ICC as a loss vector, we update via multiplicative weight updates.
We now want to bound the required number of iterations T. The MWU only guarantee approximate solution the LP with distribution ह E Av. but this is sufficient for our purposes. Indeed, the following holds:
Lemma A.2. Assume that in every iteration 1 S i B of Algorithm I, we use an approximate solution x(( with
of sc())))))> 2 _ ((1 ((1-))OPT- (
1
BEV
for all V and S V. Then, Algorithm 1 still outputs a solution such that fc(S) 2 (1 (())) for all colors E C, under the same conditions as Theorem 4.2.
Proof. The proof is simple and follows, for example, by replacing OPT by (1 c)OPT in the proof of Theorem 4.2 and related lemmas.
We therefore need to show that using sufficiently many iterations, the multiplicative weights update can obtain an approxi- mation T that satisfies the condition Lemma A.2.
We use the typical regret guarantee (for example, see Arora et al. (2012)) for MWU, which states that
min yEAC
T
((((1))))) 2 Σ t=1
T
(,(0))
log l
11(((0))12
(11)
where (!)) is the weight vector at the beginning of iteration 1, E(v) = (la(V)) E RC the loss vector as defined in (10), and (()) the best response to (t).
Lemma A.3. Using T = M2 log 2OPT2 and an appropriate choice of nj > 0, the solution I E Av is such that for all
sets 5 C V with S < B.
Σ Jofo(U 5) 2 B (
VEV
Proof. Let y = /
Ac. Note first that
1 T
T
T
7
Σ
),((1))))1)))))))))))))
+
Σ
max
max(((()
(()),
max veV
T
Σ
(f(v).
(0) -max((()) > OPT.
NEV NEr
t=1
t=
17

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
5000
LP Greedy
Greedy Minimum
60
Function eval evaluations
4000
Greedy Round Robin
Valuie min, fc(8)
Saturate
Udwani MWU
3000
55
LP Greedy
2000
Greedy Minimum
Greedy Round Robin
1000
Saturate
Udwani MWU
45
0
10
25
Budget
Budget
Figure 5. Multiobjective submodular maximization for max-k-cover. We use k = 20 Barabási-Albert graphs 64 nodes. We show the function value (top) and the number of evaluations (bottom). We report mean and standard deviation over runs.
As such, the regret guarantee (11) implies
T Σ
min eEC
(c())))
min JEDc T
Σ (((())))))) 2 OPT
log 17 T
Σ
|((()()))10
(12)
Tn
Since (v(1)) Bf((v] 8) + fc(8) < BM + OPT < 2BM it suffices set
<ОPT
and T 16 log BB
B2 log k
1 ==
8B2M
M
e2
2 16
2OPTT
so we can further bound (12) by (1 E)OP.. Therefore, we have for all C that
Σ
(B.((t + ( Σ (v(0)) 2 -1- (1-c)OPT- log k e7OPT
1 +
DEV
t=1
where the equality is by definition of and the loss E(v). Since Av. this equivalent to the statement we wanted show, done.
Theorem 4.9. Our algorithm for multiobjectivve submodular maximization runs in time O(nB3 2 log( and requires On log(1/5) ()) function evaluations.
Proof. The pre- prepprocessing takes time O(k)) since it has at most one function evaluation per color C and element U E V. Algorithm 2 runs through total of O(B log(1/6)) iterations: log(2/8) iterations of the outer loop and B iterations of the inner loop. To solve the LP in each iteration, we need the marginal gains for all colors c C' and elements v E V, which thus requires O (kn) function evaluations. We can solve the I.P approximately which, as shown in Lemma A.3, O 3 log k) iterations. Each iteration of the multiplicative weights update involves
requires T' O M ZOPT) most nk function evaluations. Overall, we thus have running time of O(nB3 3 log(k) log(1/5)) and OnnBk) function evaluations.
log
B. Further Experimental Results
B.I. Max-k-Coverage
Figures and show our results for Barabási-Alus and Erdös- -énis- random graphs, respectively. We obtain a preferential- attachment graph in the Barehé model by iteratively connecting each node = 5 existing nodes, with probability
18

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
65
8000
LP Greedy
60
Greedy Minimum
# Function evaluations
Greedy Round Robin
Value min. f.())
6000
Saturate
Udwani MWU
4000
45
Greedy
Greedy Minimum
40
Greedy Round Robin
2000
Saturate
Udwani MWU
0
10
15
20
25
30
5
10
15
20
25
30
Budget 17
Budget B
Figure Multiobjective submodular maximization max-k-cover. We use & = 20 Erdös-Rényi graphs on n = nodes. We show the function value (top) and the number of evaluations (bottom). We report and standard deviation over 5 runs.
65
LP Greedy
60-
5000
Greedy Minimum
#Function evaluations
Greedy Round Robin
Value nin, f.())
Saturate
Udwani MWU
3000
LP Greedy
Greedy Minimum
2000
Greedy Round Robin
Saturate
1000
Udwani
0
10
25
30
20
25
30
Budget
Budget
Figure 7. Multiohjective submodular maximization for max-k-cover. We 20 Rarahási-Allert graphs 64 nodes for
varying d. We show the function value (top) and the number of evaluations (bottom). We report mean and standard deviation over runs.
LP Greedy
8000
Greedy Minimum
Function evalu vvaluatioos
Greedy Round Robin
Value min...e55 (d(S)
50
Saturate
6000
Udwaní MWU
40
LP Greedy
4000
Greedy Minimum
30
Greedy Round Robin
2000
Saturate
20
Udwani MWU
0
10
15
25
30
10
15
20
25
30
Budget
Budget
Figure 8. Multiobjective submodular maximization for max max-e-cover We use & = 20 Erdös-Rén Rényi graphs on 64 nodes for varying We show the function value (top) and the number evaluations (bottom). We report mean and standard deviation runs.
19

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
1.00
10
LP Greedy
Greedy Minimum
0.95
Function eval evaluations
Greedy Round Robin
Value min. fd(8)
Saturate
0.90
10a
Udwani MWU
LP Greedy
Greedy Minimum
0.80
Greedy Round Robin
10a
Saturate
Udwani MWU
0.75
15 Budget
Budget
Figure 9. Fair centrality maximization the Amazon co-purchasing graph Movies & TV with 23 nodes and l: colors.
1.00
Greedy
10
Greedy Minimum
0.95
Functioo evaluations
Greedy Round Robin
Value min, mine f((S)
0.90
Saturate
Udwani MWU
10a
0.85
Greedy
0.80
Greedy Minimum
Greedy Round Robin
10a
0.75
Saturate
Udwani MWU
0.70
10
15
20
25
10
15 Budget B
20
25
Budget B
Figure Fair centrality maximization on the Amazon co-purchasing graph Musical Instruments with n nodes and & colors.
proportional to their degrees. We obtain random graph in the Erdös-Rényi model by including each pair as an edge with probability 0.1.
Additionally, we create more difficult synthetic instances where the graph properties differ per color. For Erdōs-Rény random graphs, create an instance where we use p. 0.1 + 50 E [0.1, 0.5] for colors S S 20 generate the e-th graph. For Barabási-Albes graphs, vary the number of d, [5 5 for colors c S 20. Our results in Figures 7 and 8 show that the our algorithm performs better under imbalance compared to heuristics such as SATURATE.
B.2. Fair Centrality Maximization
Figures 9 through 25 show omitted results Amazon co-purchasing graphs.
B.3. Fair Influence Maximization
Figures 26 through 29 show omitted results Antelope Valley network for four remaining attributes.
20

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
1.0
LP Greedy
Greedy Minimum
0.9
Function eval evaluations
10"
Greedy Round Robin
Value min. f.(S)
Saturate
Udwani MWU
0.8
10a
LP Greedy
0.7
Greedy Minimum
Greedy Round Robin
#
Saturate
10a
0.6
Udwani MWU
15
20
30
35
10
15
25
30
Budget B
Budget
Figure 11. Fair centrality maximization on the Amazon co- oo-purchasing graph All Electronics with n = 47 nodes and & 2 colors.
1.0
LP Greedy
Greedy Minimum
0.9
#Function evaluations
Greedy Round Robin
Value min, f(())
10
Saturate
Udwani MWU
0.8
Greedy
10a
0.7
Greedy Minimum
Greedy Round Robin
Saturate
0.6
Udwani MWU
10
20
30
10
50
60
10
20
30
40
50
60
Budget H
Budget B
Figure Fair centrality maximization on the Amazon co-purchasing graph Computers with m nodes colors.
1.0
LP Greedy
Greedy Minimum
0.9
Function evaluations
Greedy Round Robin
Value min, fu()
10
Saturate
0.8
Udwani MWU
LP Greedy
10a
0.7
Greedy Minimum
Greedy Round Robin
#
0.6
Saturate
Udwani MWU
10a
20
60
Budget B
Budget
Figure 13.
Fair centrality maximization the Amazon co-purchasing graph Home Audio & Theater with 77 nodes and k 2
colors.
21

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
LP Greedy
0.80
10a
Greedy Minimum
#Function evaluations
Greedy Round Robin
Value min. f((8)
Saturate
Udwani MWU
0.70
10
LP Greedy
Greedy Minimum
Greedy Round Robin
0.60
10a
Saturate
Udwani MWU
0.55
20
40
80
100
20
40
60
80
100
Budget
Budget B
Figure 14. Fair centrality maximization the Amazon co-purchasing graph Camera Photo with 202 nodes and k colors.
LP Greedy
105
Greedy Minimum
0.75
Functioo evaluations
Greedy Round Robin
Value mnin, f.(S)
0.70
Saturate
Udwani MWU
10
LP Greedy
0.60
Greedy Minimum
Greedy Round Robin
0.55
10a.
Saturate
0.50
Udwani MWU
20
60
80
100
Budget
Budget
Figure 15. Fair centrality maximization the Amazon co-purchasing graph Baby with 228 nodes and k colors.
LP Greedy
Greedy Minimum
# Function vaaluations
Greedy Round Robin
Value min. fdS)
10
Saturate
0.55
Udwani MWU
Greedy
0.50
Greedy Minimum
10c
Greedy Round Robin
Saturate
Udwani MWU
10a
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Budget
Budget B
Figure 16. Fair centrality maximization on the Amazon co-purchasing graph Luxury Beauty with n -1037 nodes and 2 colors.
22

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
0.373
10a
LP Greedy
Greedy Minimum
0.550
Function eval evaluations
Greedy Round Robin
Value min. f.(S)
0.525
Saturate
Udwani MWU
10
0.500
LP Greedy
0.475
Greedy Minimum
Greedy Round Robin
#
0.450-
10
Saturate
Udwani MWU
25
50
75
100
125
150
175
50
75
100
150
175
200
Budget B
Budget
Figure 17. Fair centrality maximization on the Amazon co- po-purhhasing graph Per Supplies with n = 1785 nodes and & 2 colors.
0.65
LP Greedy
106
Greedy Minimum
0.60
#Function evaluations
Greedy Round Robin
Value min, f((S)
Saturate
Udwani MWU
0.55
105
LP Greedy
Greedy Minimum
0.50
Greedy Round Robin
Saturate
0.45
Udwani MWU
100
200
300
400
500
100
200
300
100
500
Budget
Budget B
Figure colors.
Fair centrality maximization Amazon co-purchasing graph Industrial Scientific with n 2005 nodes
0.65
10a
LP Greedy
Greedy Minimum
Function evaluations
Greedy Round Robin
Value min, f.(S)
0.60
Saturate
10
Udwani MWU
0.55
LP Greedy
Greedy Minimum
Greedy Round Robin
10
Saturate
Udwani MWU
400
500
Budget
Budget
Figure 19, Fair centrality maximization the Amazon co-purchasing graph Office Products with 2281 nodes and A: 2 colors.
23

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
LP Greedy
0.60
Greedy Minimum
Function evaluations
Greedy Round Robin
Value min. fc(S)
Saturate
Udwani MWU
0.50
10
LP Greedy
0.45
Greedy Minimum
Greedy Round Robin
#
Saturate
10
0.10
Udwani MWU
100
500
200
300
400
500
Budget
Budget
Figure 20. Fair centrality maximization on the Amazon co- po-purrcaaing graph Books with = 2495 nodes and = 2 colors.
0.65
LP Greedy
10"
Greedy Minimum
#Function evaluations
Greedy Round Robin
Value min, f.(S)
Saturate
0.55
Udwani MWU
10
0.50
Greedy
Greedy Minimum
Greedy Round Robin
Saturate
10
Udwani MWU
0.40
100
200
300
400
500
100
200
300
100
500
Budget
Budget B
Figure Fair centrality maximization on Amazon co-purchasing graph Home Improvement with 2565 nodes k: colors.
LP Greedy
Greedy Minimum
# Function evaluations
10
Greedy Round Robin
Value min, fd(S)
Saturate
0.50
Udwani MWU
LP Greedy
10a
0.45
Greedy Minimum
Greedy Round Robin
Saturate
10a
Udwani
400
Budget
Budget
Figure 22.
Fair centrality maxinization the Amazon co-purchasing graph Health Personal Care with 3010 nodes and A: 2
colors.
24

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
0.60
LP Greedy
Greedy Minimum
# #uunction evaluations
10e
Greedy Round Robin
Value min, (.())
0.55
Saturate
Udwani MWU
0.50
LP Greedy
10
Greedy Minimum
0.45
Greedy Round Robin
Saturate
0.40
Udwani MWU
10"
100
200
300
400
500
100
200
300
400
500
Budget
Budget B
Figure 23. Fair centrality maximization on the Amazon co-purchasing graph Sports & Outdoors with 3224 nodes and k colors.
LP Greedy
Greedy Minimum
Function evaluations
10"
Greedy Round Robin
Value min, f.(S)
0.55
Saturate
Udwani MWU
0.50
LP Greedy
10a
Greedy Minimum
0.45
Greedy Round Robin
Saturate
Udwani MWU
10
200
400
1000
400
600
800
1000
Budget
Budget
Figure 24. Fair centrality maximization the Amazon co-purchasing graph Grocery with 6433 nodes and k colors.
10P
LP Greedy
0.525
Greedy Minimum
0.500
# Function eval vvlluatoons
Greedy Round Robin
Value min,, f.8)
Saturate
0.475
105
Udwani MWU
0.450
Greedy
0.425
Greedy Minimum
0.400
Greedy Round Robin
10a
Saturate
0.375
Udwani MWU
200
400
600
800
1000
200
400
600
800
1000
Budget B
Budget B
Figure 25. Fair centrality maximization on the Amazon co co-purchasing graph Amazon Home with n 10337 nodes and k colors.
25

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
0.30
LP Greedy
0.25
200
Greedy Minimum
Greedy Round Robin
Value min, (.8)
0.20
Running time [s]
150
Tsang al. FW
Saturate
LP Greedy
100
0.10
Greedy Minimum
Greedy Round Robin
50
0.05
Tsang al. FW
Saturate
0.00
0-
10
20
40
10
20
30
40
50
Budget
Budget B
Figure 26.
Fair influence maximization simulated Antelope Valley network with attribute age on l colors.
0.30
LP Greedy
200
Greedy Minimum
0.25
Greedy Round Robin
Value min, f.(S)
Running time [d]
150
Tsang et al. FW
Saturate
LP Greedy
100
Greedy Minimum
0.10
Greedy Round Robin
Tsang et al. FW
0.05
Saturate
10
10
20
30
40
50
Budget
Budget B
Figure 27. Fair influence maximization simulated Antelope Valley network with attribute gender on k: 2 colors.
0.30
LP Greedy
200
LP Greedy
0.25
Greedy Minimum
Greedy Minimum
Greedy Robin
Greedy Round Robin
Value min. fe(S)
0.20
Tsang et al. FW
Running time [s]
150
Tsang
Saturate
Saturate
0.15
100
0.10
50-
0.05
0.00
10
20
30
40
50
10
20
30
40
50
Budget
Budget B
Figure 28. Fair influence maximization on a simulated Antelope Valley network with attribute region on & 13 colors.
26

---

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
0.30
175
LP Greedy
150
Greedy Minimum
0.25
Greedy Round Robin
Value min,, f.(S)
Running time [d]
125
Tsang et al. FW
0.20
100
Saturate
0.15
LP Greedy
Greedy Minimum
0.10
Greedy Round Robin
Tsang et al. FW
25
0.05
Saturate
10
20
30
40
50
Budget
Budget
Figure 29. Fair influence maximization simulated Antelope Valley network with attribute status k = 3 colors
27


Reviews:
[{"review_id": "uhlCAQN0pZ", "reviewer": "Reviewer_1Lvm", "summary": "A combinatorial algorithm for multi-objective submodular optimization is developed, that achieves ratio 1-1/e with constant problem under assumptions on the budget and number of colors. This improves over the best ratio achieved by a combinatorial algorithm in prior work. The algorithm requires several novel ideas. A new application of fair centrality is introduced, and an empirical evaluation of the algorithm is included.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your evaluation and the encouraging comments on the strengths of our paper.\n\n> This work isn't essential, but I would appreciate a discussion of [1], as elaborated in strengths and weaknesses.\n> [1]. Buchbinder, Niv, et al. \"Submodular maximization with cardinality constraints.\" Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014.\n> I do think it would be a good idea to cite [1] and explain the relationship between the algorithms.\n> Would like to see [1] cited and a discussion of the relationship between the combinatorial algorithm (RandomGreedy) in that paper and this one. Could ideas from RandomGreedy (which works for non-monotone objective) extend to a non-monotone variant of the algorithm in this paper?\n\nA similarity is that we sample randomly, but our sampling probabilities are carefully chosen to solve the multiobjective problem. One way to see the difference between the algorithms (in terms of the goal and design of either algorithm) is if we run our algorithm for only a single color. Then our algorithm reduces to greedy, showing that our sampling is designed only to enforce good progress across all colors. Their sampling is (intuitively) intended to avoid adding “bad elements” to the solution. However, we believe it could be a promising idea to combine both sampling strategies to obtain an algorithm for non-monotone multiobjective maximization. We will add such a discussion to our paper.\n\n> line 107: seting -> setting It might be a good idea if B > k, or the approximability of the problem were discussed earlier. When reading Problem 3.1, I was wondering about this. If B < k, clearly inapproximable.\n\nIn a revised version, we will fix the typo and state after Problem 3.1 that we are interested in the case where the budget is large compared to k ($B>k$).\n\n> Is there a direction transformation from the notion of fairness as a constraint (as in some of the references discussed in the introduction) to the multi-objective notion of fairness? If so, how do the results in those papers compare with this one?\n\nFairness as a constraint is enforced on the solution set itself. For instance, one can require that the intersection of the solution set with each group (groups are subsets of the ground set) has a certain size. The multiobjective problem is different in that it asks for fairness in the objectives, which corresponds to the notion of max-min fairness on the outcomes. As such, we do not think that one problem can be cast as the other.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked the results in the main text through Section 4.1. I even tried to come up with a simpler version of the algorithm that avoided an LP, which didn't end up working.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "Improves the state-of-the-art ratio for a combinatorial algorithm for this problem.", "essential_references_not_discussed": "This work isn't essential, but I would appreciate a discussion of [1], as elaborated in strengths and weaknesses.\n\n[1]. Buchbinder, Niv, et al. \"Submodular maximization with cardinality constraints.\" Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014.", "other_strengths_and_weaknesses": "Strengths:\n+ Paper is well written and easy to follow. Contributions are clearly explained and the relationship to prior work is well documented.\n+ The main algorithm reminds me a lot of the RandomGreedy algorithm from [1], with some novel differences. RandomGreedy samples a random element from the top k marginal gains to get one with good enough average contribution. This algorithm requires solving an LP to obtain a probability distribution to sample from. Additional ideas are needed to get a bound that holds with constant probability. I do think it would be a good idea to cite [1] and explain the relationship between the algorithms.\n+ I found the fair centrality application interesting, and the experimental results clearly show the advantages of the proposed algorithm.\n+ I also appreciated an interpretation of fairness in terms of multi-objective optimization, rather than enforcing it through various contraints.\n\n[1]. Buchbinder, Niv, et al. \"Submodular maximization with cardinality constraints.\" Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014.\n\nWeaknesses:\n+ Would like to see [1] cited and a discussion of the relationship between the combinatorial algorithm (RandomGreedy) in that paper and this one. Could ideas from RandomGreedy (which works for non-monotone objective) extend to a non-monotone variant of the algorithm in this paper?/", "other_comments_or_suggestions": "line 107: seting -> setting\nIt might be a good idea if B > k, or the approximability of the problem were discussed earlier. When reading Problem 3.1, I was wondering about this. If B < k, clearly inapproximable.", "questions_for_authors": "- See weaknesses.\n- Is there a direction transformation from the notion of fairness as a constraint (as in some of the references discussed in the introduction) to the multi-objective notion of fairness? If so, how do the results in those papers compare with this one?", "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": "0eXAwDmPHb", "reviewer": "Reviewer_vgBn", "summary": "They study the multiobjective monotone submodular maximization under cardinality constraint, where the goal is to select a subset of elements of limited size that maximizes the minimum submodular value among the given functions. Previously, a $(1-\\frac{1}{e})$-approximation algorithm was known for this problem using multilinear extension which is impractical. Moreover, there was a practical $(1-\\frac{1}{e})^2$-approximation algorithm for this problem. Here they develop a $(1-\\frac{1}{e}-\\epsilon)$-approximation algorithm which relies on selecting elements step by step. At each step, they try to solve an LP to find a probability distribution which identifies the weight of selecting elements to increase the submodular value enough. This is similar to selecting an element with a marginal gain above a threshold, but in this case, it is more complex as it requires finding a probability distribution via an LP. Finally, they select an element using this probability distribution and add it to their solution.\n\nSince their approach is randomized, they run it multiple times to find a desired solution with higher probability. Note that their algorithm has |B| steps, where |B| is the cardinality constraint. At each step, they run a LP which is time consuming and needs to find marginal value of all elements compared to their current solution. However, they have introduced a lazy update method using multiplicative weights update (MWU) to speed up their algorithm.\n\nFinally, they show the efficiency of their approach with experimental evaluation. In their evaluation, they beat the previous practical algorithms with approximation guarantee. However, it seems a greedy heuristics algorithm finds almost the same submodular value, while having better running time and query complexity. This greedy algorithm tries to select an element that maximizes the submodular value of the function that has the current minimum value.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and the positive feedback on our presentation.\n\n> However, it seems a greedy heuristics algorithm finds almost the same submodular value, while having better running time and query complexity. \n\n> The only weakness is that the greedy minimum algorithm seems to outperform their algorithm in experiments but since that one does not have an approximation guarantee, still their algorithm and its analysis remain interesting.\n\nWhile the greedy heuristic does obtain high objective value, there is a long line of work on the multiobjective problem which aims to improve upon greedy heuristics (Leskovec et al. ‘10; Chekuri et al. ‘10; Orlin et al. ‘18; Udwani ‘18; Tsang et al. ‘19). We contribute to this line of work by providing the first practical algorithm with the best possible approximation guarantee. Although greedy might perform similarly in practice it does not have any theoretical guarantees, as the reviewer points out. Such guarantees are valuable as they ensure that we consistently perform well on any given instance. In particular, we outperform or match greedy in objective value.", "claims_and_evidence": "They proved their lemmas and claims and also ran experiments to show their dominance compared to previous practical works.", "methods_and_evaluation_criteria": "The methods make sense. They could run experiments on larger instances, especially since the multilinear extension approach despite having the same approximation guarantee is impractical on large instances.", "theoretical_claims": "I only checked the proofs in the main part of the paper and not the appendix and they seem fine.", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "While there was an algorithm with the same approximation guarantee, it was not practical and the previous practical algorithms had worse approximation factors. They could develop a practical algorithm that matches the best known approximation factor for this problem.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "I like their algorithm, it seems natural and achieves the best known approximation factor for submodular maximization. The paper is very well written and easy to follow and understand. The only weakness is that the greedy minimum algorithm seems to outperform their algorithm in experiments but since that one does not have an approximation guarantee, still their algorithm and its analysis remain interesting.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "xUOlDIY2HE", "reviewer": "Reviewer_roJW", "summary": "This paper addresses the problem of maximizing the minimum over several submodular functions, known as multiobjective submodular maximization. The authors present the first scalable algorithm that achieves the best-known approximation guarantee. Additionally, they introduce a novel application—fair centrality maximization—and demonstrate how it can be effectively addressed through multiobjective submodular maximization.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for evaluation and the positive comments on our writing and the scalability of our approach.\n\n> The technical novelty of the work seems marginal. While the proposed solution outperforms existing studies in terms of lower running time and improved approximation ratio, the fundamental design and analysis of the algorithm appear to be inspired by previous work, such as Chekuri et al. (2010). Moreover, the results of Chekuri et al. (2010) can be applied to a broader range of constraints, such as matroid constraints. Additionally, I believe their results do not rely on the budget constraint $B$.\n\nOur method and swap rounding (due to Chekuri et al. (2010) and also used in later works, e.g. in Tsang et al. (2019)) are **different approaches** towards the multiobjective problem. The idea of swap rounding is to build a fractional solution (which they find using gradient ascent over the multilinear extension) and in the last step round it to a discrete solution. Our method adds one (discrete) element in each iteration. This leads to important differences in both the running time and the analysis of both approaches. Since we do not optimize over the multilinear extension, our approach is decisively faster: We only need $O(nBk)$ function evaluations compared to exponentially many queries (and exponential runtime) of Chekuri et al. (2010). We also carry out a different martingale analysis that is tailored to the greedy algorithm. Furthermore, their algorithm also depends on $B$ to establish their approximation guarantee, which is natural for the multiobjective problem to avoid the inapproximability regime ($B<k$) shown by Krause et al. (2008). Another natural reason for a dependence on the budget in swap rounding is that the Chernoff bound obtains better concentration for larger budgets, even for linear functions.\n\n> The paper lacks a direct comparison between their method and the one proposed in Chekuri et al. (2010) in the experimental section. While I understand that Chekuri et al. (2010)’s algorithm may not be practical due to its reliance on multilinear extensions, I would have appreciated seeing some comparative results in a small- or medium-scale setting to better understand the trade-offs.\n\nWe compare our paper with the approach of Tsang et al. (2019) which provides a practical implementation of the approach of Chekuri et al. (2010) by performing gradient ascent efficiently via Frank-Wolfe. Their parameters are chosen to make the algorithm practical on special medium-sized instances (their algorithm does not apply to general applications such as fair centrality maximization, which is why we exclude it there). However, their algorithm is still slower and has worse objective value than our algorithm, suggesting that the trade-offs of the unrefined approach of Chekuri et al. (2010) are also poor.", "claims_and_evidence": "+The paper tackles an important problem in the field of submodular optimization, with results that can be applied to solving fairness-aware subset selection problems.\n+The paper is well-written, with the algorithm presented in a clear and easy-to-follow manner. The analysis is also clearly outlined. Notably, the algorithm is both scalable and effective, achieving the best approximation ratio without relying on continuous relaxation of the submodular set functions.\n\nHowever, there are some points of concern:\n\n-The technical novelty of the work seems marginal. While the proposed solution outperforms existing studies in terms of lower running time and improved approximation ratio, the fundamental design and analysis of the algorithm appear to be inspired by previous work, such as Chekuri et al. (2010). Moreover, the results of Chekuri et al. (2010) can be applied to a broader range of constraints, such as matroid constraints. Additionally, I believe their results do not rely on the budget constraint B.\n\n-The paper lacks a direct comparison between their method and the one proposed in Chekuri et al. (2010) in the experimental section. While I understand that Chekuri et al. (2010)’s algorithm may not be practical due to its reliance on multilinear extensions, I would have appreciated seeing some comparative results in a small- or medium-scale setting to better understand the trade-offs.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The paper tackles an important problem in the field of submodular optimization, with results that can be applied to solving fairness-aware subset selection problems.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "NA.", "other_comments_or_suggestions": "NA.", "questions_for_authors": "Please refer to my comments in Claims And Evidence.", "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": "WabH36Tthy", "reviewer": "Reviewer_oK8n", "summary": "The paper develops a discrete, scalable algorithm for multiobjective submodular maximization under a cardinality constraint that nearly achieves the optimal (1−1/e) approximation ratio. Instead of relying on continuous relaxations such as the multilinear extension, the proposed approach builds the solution iteratively by solving a linear program at each step to derive a probability distribution over candidate elements, sampling from this distribution, and adding the chosen element to the solution. The algorithm incorporates multiplicative weights updates (MWU) and lazy evaluations to reduce the number of function evaluations, thereby enhancing its efficiency. As an additional contribution, the paper introduces an application to fair centrality maximization, which generalizes standard centrality measures by ensuring fairness across different groups.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and pointing out that our algorithm outperforms existing methods in terms of running time.\n\n> The query complexity of O(nBk) appears suboptimal since B approaches n, potentially resulting in quadratic complexity. This does not seem sufficiently efficient for practical applications. The authors should consider developing an approximation with near-linear complexity, which would be more meaningful and applicable in practice.\n\n> While the proposed algorithm is faster than existing methods, its time complexity remains suboptimal for handling the massive data sets encountered in real-world applications. \n\nA running time of $O(nB)$ is natural for the greedy algorithm which is a standard algorithm in practice and is widely applied on huge datasets. A running time of $O(nBk)$ is therefore quite natural on $k$ objectives. Even in the case where $B=\\Omega(n)$, our algorithm still has significantly better running time than all prior works that offer the same approximation guarantee (Chekuri et al. ‘10, the $1-1/e$ algorithm of Udwani ‘18, Tsang et al. ‘19). \n\nAs shown in our experiments, our algorithm is vastly more performant than prior work with theoretical guarantees. We are the first to provide an algorithm that scales to ten thousands of nodes (and potentially more; the running time of our algorithm on the largest instances we tried is not yet prohibitive) while providing the best possible approximation ratio.\n\n> However, its runtime is inferior compared to the other two greedy-based algorithms, namely Greedy Minimum and Greedy Round Robin. Additionally, the datasets used in the paper are relatively small, making it difficult to evaluate the efficiency of the algorithms in real-world large-scale environments.\n\nAs compared to greedy, our algorithm has theoretical guarantees. We outperform all algorithms with comparable theoretical guarantees in terms of running time, which form a long line of work that improves upon the objective value of the greedy algorithm.\n\nThe biggest instance in our experiments has $n=10378$ elements which is substantially larger than any of the instances used in the literature on multiobjective submodular maximization with theoretical guarantees (before us, the largest instance appears in Udwani ‘2018 with $n=1024$ elements). \n\n> However, some important works in this area have been overlooked, such as [1][2].\n> [1] Fazzone, A., Wang, Y., & Bonchi, F. (2024). Fair Representation in Submodular Subset Selection: A Pareto Optimization Approach. Transactions on Machine Learning Research.\n> [2] Cui, Shuang, et al. \"Fairness in streaming submodular maximization subject to a knapsack constraint.\" Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.\n\nWe will cite these papers in our related work along the following discussion:\n- [1] solves a multi-objective problem by extending the saturate algorithm to obtain a sequence of approximately pareto-optimal solutions, while our algorithm gives a single solution for the (max-min) multiobjective problem.\n- [2] considers a fairness notion that enforces constraints on the solution set. (We will add [2] alongside similar works that we cite in our related work section (e.g., Celis et al. ‘18)).", "claims_and_evidence": "The query complexity of O(nBk) appears suboptimal since B approaches n, potentially resulting in quadratic complexity. This does not seem sufficiently efficient for practical applications. The authors should consider developing an approximation with near-linear complexity, which would be more meaningful and applicable in practice.", "methods_and_evaluation_criteria": "While the proposed algorithm is faster than existing methods, its time complexity remains suboptimal for handling the massive data sets encountered in real-world applications. Nevertheless, the paper offers a promising conceptual framework that could inspire further advancements in this area.", "theoretical_claims": "I have conducted a preliminary review of the theoretical proofs in the paper, and they appear to be correct. However, I should note that my examination was not exhaustive, and there remains a possibility that some details may have been overlooked.", "experimental_designs_or_analyses": "The algorithm proposed in the paper demonstrates promising performance in terms of objective function value. However, its runtime is inferior compared to the other two greedy-based algorithms, namely Greedy Minimum and Greedy Round Robin. Additionally, the datasets used in the paper are relatively small, making it difficult to evaluate the efficiency of the algorithms in real-world large-scale environments.", "relation_to_broader_scientific_literature": "The problem addressed in this paper is related to fair submodular optimization, which involves optimizing a submodular function under fairness constraints. However, some important works in this area have been overlooked, such as [1][2].\n\n[1] Fazzone, A., Wang, Y., & Bonchi, F. (2024). Fair Representation in Submodular Subset Selection: A Pareto Optimization Approach. Transactions on Machine Learning Research.\n\n[2] Cui, Shuang, et al. \"Fairness in streaming submodular maximization subject to a knapsack constraint.\" Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.", "essential_references_not_discussed": "Please refer to the above.", "other_strengths_and_weaknesses": "N.A.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "Please refer to the above.", "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:

Meta-review: The reviewers found the problem studied important, the algorithms elegant and convincing, and the writing clear.
Decision: Accept (poster)