# Balancing Utility and Fairness in Submodular Maximization

Yanhao Wang  0000-0002-7661-3917 East China Normal UniversityShanghaiChina
<EMAIL_ADDRESS>,  Yuchen Li  0000-0001-9646-291X Singapore Management
UniversitySingaporeSingapore<EMAIL_ADDRESS>,  Francesco Bonchi
0000-0001-9464-8315 CENTAI Institute Turin ItalyEurecat Barcelona Spain
<EMAIL_ADDRESS>and  Ying Wang  East China Normal UniversityShanghaiChina
<EMAIL_ADDRESS>
###### Abstract.

Submodular function maximization is a fundamental combinatorial optimization
problem with plenty of applications – including data summarization, influence
maximization, and recommendation. In many of these problems, the goal is to
find a solution that maximizes the average utility over all users, for each of
whom the utility is defined by a monotone submodular function. However, when
the population of users is composed of several demographic groups, another
critical problem is whether the utility is fairly distributed across different
groups. Although the _utility_ and _fairness_ objectives are both desirable,
they might contradict each other, and, to the best of our knowledge, little
attention has been paid to optimizing them jointly.

To fill this gap, we propose a new problem called _Bicriteria Submodular
Maximization_ (BSM) to balance utility and fairness. Specifically, it requires
finding a fixed-size solution to maximize the utility function, subject to the
value of the fairness function not being below a threshold. Since BSM is
inapproximable within any constant factor, we focus on designing efficient
instance-dependent approximation schemes. Our algorithmic proposal comprises
two methods, with different approximation factors, obtained by converting a
BSM instance into other submodular optimization problem instances. Using real-
world and synthetic datasets, we showcase applications of our proposed methods
in three submodular maximization problems: maximum coverage, influence
maximization, and facility location.

††copyright: rightsretained

##  1\. Introduction

The awareness that decisions informed by data analytics could have inadvertent
discriminatory effects against particular demographic groups has grown
substantially over the last few years (Jagadish et al., 2019). Researchers
have been studying how to inject _group fairness_ , along the lines of
_demographic parity_ (Dwork et al., 2012) or _equal opportunity_ (Hardt et
al., 2016), into algorithmic decision-making processes. The bulk of this
algorithmic fairness literature has mainly focused on avoiding discrimination
against a sensitive attribute (i.e., a protected social group) in supervised
machine learning (Kearns et al., 2017), while less attention has been devoted
to combinatorial optimization problems such as ranking (Asudeh et al., 2019),
selection (Emelianov et al., 2022), allocation (Mashiat et al., 2022), and
matching (García-Soriano and Bonchi, 2020; Esmaeili et al., 2022).

In this paper, we study how to incorporate group fairness into _submodular
maximization_ (Krause and Golovin, 2014) (SM), one of the most fundamental
combinatorial optimization problems. Specifically, a set function is
submodular if it satisfies the “ _diminishing returns_ ” property, whereby the
marginal gain of adding any new item decreases as the set of existing items
increases. More formally, a set function $f:2^{V}\rightarrow\mathbb{R}_{\geq
0}$ defined on a ground set $V$ of items is submodular if
$f(S\cup\\{v\\})-f(S)\geq f(T\cup\\{v\\})-f(T)$ for any two sets $S\subseteq
T\subseteq V$ and item $v\in V\setminus T$. This property occurs in numerous
data science applications, such as data summarization (Badanidiyuru et al.,
2014), influence maximization (Kempe et al., 2003), and recommendation
(Parambath et al., 2018).

Submodular maximization with a cardinality constraint is the most widely
studied optimization problem on submodular functions. For a monotone
submodular function $f$ and a cardinality constraint $k\in\mathbb{Z}^{+}$, it
aims to find a size-$k$ subset $S\subseteq V$ of items such that $f(S)$ is
maximized. Although this problem is generally NP-hard (Feige, 1998), the
classic greedy algorithm (Nemhauser et al., 1978) yields a best possible
$(1-1/e)$-approximation factor.

In many scenarios, the goal of a submodular maximization problem is to find a
good solution to serve a large number of users, for each of whom the utility
is measured by a monotone submodular function. For such problems, the classic
greedy algorithm is effective in maximizing the _average utility_ over all
users (called the _utility objective_) because it is a non-negative linear
combination of monotone submodular functions, which is still monotone and
submodular (Krause and Golovin, 2014). However, when users are composed of
different demographic groups, the utilities should be _fairly distributed_
across groups to avoid biased outcomes (Kleinberg et al., 2019). A typical
choice for the _fairness objective_ is to improve the welfare of the least
well-off group, as per Rawls’s theory of justice (Rawls, 1971), which
advocates arranging social and financial inequalities so that they are to the
greatest benefit of the worst-off. The problem of maximizing the minimum
utility among all groups coincides with _robust submodular maximization_
(Krause et al., 2008; Udwani, 2018; Tsang et al., 2019) (RSM), which is
inapproximable within any constant factor in general but admits approximate
solutions by violating the cardinality constraints (i.e., providing solutions
of sizes larger than $k$).

Although the two objectives of _utility_ and _fairness_ , when taken in
isolation, can be treated as SM and RSM instances, respectively, optimizing
them jointly results to be a much more challenging task, as maximizing one can
come at the expense of significantly reducing the other. To our best
knowledge, there has been no prior investigation into optimizing both
objectives jointly.

To fill this gap, we propose a new problem called _Bicriteria Submodular
Maximization_ (BSM) to balance utility and fairness. As is often the case when
facing two opposite objectives (Ohsaka and Matsuoka, 2021; Gershtein et al.,
2021; Wei et al., 2015), the BSM problem requires finding a fixed-size
solution to maximize the utility function subject to that the value of the
fairness function is at least a $\tau$-fraction of its optimum for a given
factor $\tau\in[0,1]$.

Our proposal can find application in many real-world submodular maximization
problems, such as:

  * •

Maximum Coverage (MC) is a well-known NP-hard problem with broad applications
in summarization and recommendation (Saha and Getoor, 2009; Serbos et al.,
2017). Given a collection of sets over the same ground set, it selects a set
of $k$ sets such that their union contains as many elements as possible. When
the ground set is a set of individuals divided into different population
groups, we also need the solution to cover individuals from every group
proportionally (Asudeh et al., 2023; Bandyapadhyay et al., 2021) for equitable
representation. By combining both objectives, we formulate a new problem of
maximizing the total coverage of all users and the minimum average coverage
for all groups simultaneously.

  * •

Influence Maximization (IM) arises naturally in the design of viral marketing
campaigns in social networks (Kempe et al., 2003). The IM problem (Kempe et
al., 2003; Li et al., 2018) asks to find a set of $k$ “seed” users in a social
network so that, if they are targeted by the campaign, the expected influence
spread in the network is maximized. Recent studies (Tsang et al., 2019; Becker
et al., 2020) introduced group fairness into IM, aimed at balancing the spread
of influence among different population groups to reduce information
inequality. In such context, BSM corresponds to a new problem of achieving a
better trade-off between the influence spread among all users and the
influence spread within the least well-off group.

  * •

Facility Location (FL) aims at finding a set of items to maximize the total
benefits for all users: it finds application in data clustering and location-
based services (LBSs) (Badanidiyuru et al., 2014; Thejaswi et al., 2021;
Lindgren et al., 2016). In submodular facility location problems, the benefit
of an item set to a user is defined as the maximum benefit among all items in
the set to the user. As an illustrative example, a set of service points
deployed in a district can lead to higher benefits for citizens whose
residences are closer to their nearest service points. To achieve group-level
fairness, it should ensure that each group of users receives approximately the
same benefits on average. As such, BSM finds a set of items that maximizes the
benefits for all users and the least well-off group to balance utility and
fairness in facility location.

Contributions & Roadmap. We first formally define the bicriteria submodular
maximization (BSM) problem: Given two functions $f,g$ to measure the _average
utility_ for all users and the _minimum utility_ among all groups,
respectively, and a balance factor $\tau\in[0,1]$, it asks for a size-$k$ set
$S\subseteq V$ to maximize $f(S)$, subject to that
$g(S)\geq\tau\cdot\mathtt{OPT}_{g}$, where
$\mathtt{OPT}_{g}=\max_{S^{\prime}\subseteq V,\lvert
S^{\prime}\rvert=k}g(S^{\prime})$. We then prove that BSM cannot be
approximated within any constant factor for all $\tau>0$ and $k\geq 1$
(Section 3).

Due to the inapproximability of BSM, we focus on designing efficient instance-
dependent approximation schemes for BSM. Specifically, we first propose a two-
stage greedy algorithm combining the two greedy algorithms for _submodular
maximization_ (Nemhauser et al., 1978) and _submodular cover_ (Wolsey, 1982),
for maximizing $f$ and $g$ in turn to obtain a BSM solution (Section 4.1).
Then, we devise an improved algorithm with a better approximation ratio at the
expense of violating the cardinality constraint by converting a BSM instance
into several _submodular cover_ (Wolsey, 1982) instances and running the
Saturate algorithm (Krause et al., 2008) for submodular cover to find a BSM
solution (Section 4.2). We also analyze the approximation factors and
computational complexities of both algorithms. Moreover, we formulate specific
classes of BSM problems, i.e., _maximum coverage_ and _facility location_ , as
integer linear programs (ILPs), thus acquiring their optimal solutions on
small instances using any ILP solver (Appendix A). This can help quantify the
gap between the optimal and approximate solutions to BSM in practice.

Finally, we conduct extensive experiments to evaluate the proposed algorithms
on three submodular maximization problems, namely _maximum coverage_ ,
_influence maximization_ , and _facility location_ , using real-world and
synthetic datasets in comparison to non-trivial baselines, including
approximation algorithms for SM (Nemhauser et al., 1978), RSM (Krause et al.,
2008), and submodular maximization under submodular cover (Ohsaka and
Matsuoka, 2021) (SMSC). Our experimental results demonstrate that our
algorithms offer better trade-offs between the utility and fairness objectives
than the competing algorithms and are scalable against large datasets (Section
5).

Our main technical contributions are summarized as follows:

  1. (1)

The definition of the bicriteria submodular maximization (BSM) problem to
balance utility and fairness in submodular maximization.

  2. (2)

The proof of the inapproximability of BSM.

  3. (3)

Two instance-dependent approximation algorithms for BSM with theoretical
analyses of their approximation factors and complexities as well as problem-
specific ILP formulations for BSM.

  4. (4)

Comprehensive experimental results to verify the effectiveness and efficiency
of our proposed BSM framework and algorithms in real-world applications.

##  2\. Related Work

Before presenting our technical results, we first collocate our contribution
to the literature by discussing the related work.

Submodular Maximization (SM). Maximizing a monotone submodular function with a
cardinality constraint $k$ is one of the most widely studied problems in
combinatorial optimization. A simple greedy algorithm (Nemhauser et al., 1978)
runs in $\mathcal{O}(nk)$ time and provides the best possible
$(1-1/e)$-approximate solution for this problem unless $P=NP$ (Feige, 1998).
Several optimization techniques, e.g., _lazy forward_ (Leskovec et al., 2007)
and _subsampling_ (Mirzasoleiman et al., 2015), were proposed to improve the
efficiency of the greedy algorithm. Any of the above algorithms can be used as
a subroutine in our algorithmic frameworks for BSM. Furthermore, there have
been approximation algorithms for submodular maximization problems with more
general constraints beyond cardinality, such as _knapsack_ (Tang et al.,
2021), _matroid_ (Călinescu et al., 2011), _$k$ -system_ (Cui et al., 2021),
and more (Mirzasoleiman et al., 2016a). In addition, submodular maximization
problems were also studied in various settings, including the _streaming_
(Badanidiyuru et al., 2014), _distributed_ (Mirzasoleiman et al., 2016b),
_dynamic_ (Monemizadeh, 2020), and _sliding-window_ (Epasto et al., 2017; Wang
et al., 2019, 2017) models. However, unlike our BSM problem, all the above
problems only consider maximizing a single submodular objective function.

Previous work (El Halabi et al., 2020; Wang et al., 2021) has also introduced
fairness into submodular maximization problems. Specifically, they considered
that the items to select represent persons and are partitioned into several
demographic groups based on sensitive attributes and proposed efficient
approximation algorithms to find a set of items for maximizing a submodular
function subject to the constraint that the number of items chosen from each
group must fall within the pre-defined lower and upper bounds to achieve an
equal (or proportional) group representation in the solution. Nevertheless,
such a notion of fairness is distinct from ours. In our BSM problem, the items
are assumed to be non-sensitive; thus, no specific restriction is imposed on
the attributes of items to pick in the solution. We alternatively focus on
picking a fixed-size set of items to distribute utilities fairly across
sensitive user groups. Due to the differences in data models and fairness
notions, the algorithms in (El Halabi et al., 2020; Wang et al., 2021) are not
comparable to those in this paper and thus ignored in the experimental
evaluation.

Robust Submodular Maximization (RSM). The problem of _robust (or multi-
objective) submodular maximization_ aims to maximize the minimum of $c>1$
submodular functions. The RSM problem is inapproximable within any constant
factor in polynomial time unless $P=NP$ (Krause et al., 2008). The algorithms
that provide approximate solutions for RSM by violating the cardinality
constraints were proposed in (Krause et al., 2008; Torrico et al., 2021). The
_multiplicative weight updates_ (MWU) algorithms for RSM, which achieves
constant approximation factors when $c=o(k\log^{-3}{k})$, were developed in
(Udwani, 2018; Fu et al., 2021). In this paper, our second algorithm for BSM
adopts a similar scheme to that for RSM in (Krause et al., 2008). But the
analyses are different because an additional objective of maximizing the
average utility is considered.

The deletion-robust submodular maximization problem (Mirzasoleiman et al.,
2017; Kazemi et al., 2018), which aims to maintain a “robust” solution when a
part of the data may be adversarially deleted, is also identified as RSM in
the literature. However, this is a different problem, and the algorithms in
(Mirzasoleiman et al., 2017; Kazemi et al., 2018) do not apply to BSM.

Submodular Optimization with More Than One Objective. There exist several
other variants of submodular optimization problems to deal with more than one
objective. Iyer and Bilmes (Iyer and Bilmes, 2012) studied the problem of
minimizing the difference between two submodular functions. Approximation
algorithms proposed in (Jin et al., 2021; Nikolakaki et al., 2021) aim to
maximize the difference between a submodular utility function and a modular
cost function. Bai _et al._ (Bai et al., 2016) considered minimizing the ratio
of two submodular functions. Iyer and Bilmes (Iyer and Bilmes, 2013)
investigated the problem of maximizing a submodular utility function while
minimizing a submodular cost function.

The most related problem to BSM is _submodular maximization under submodular
cover_ (Ohsaka and Matsuoka, 2021) (SMSC), which finds a fixed-size solution
to maximize one submodular function under the constraint that the value of the
other submodular function is not below a given threshold. A similar problem to
SMSC was also defined by Gershtein _et al._ (Gershtein et al., 2021) in the
context of influence maximization. BSM differs from SMSC as the minimum of
$c>1$ submodular functions is not a submodular function, and thus the
theoretical results for SMSC (Ohsaka and Matsuoka, 2021; Gershtein et al.,
2021) do not hold for BSM. Nonetheless, SMSC can be treated as a special case
of BSM when $c=2$, i.e., there are only two groups of users. Thus, our
experiments empirically compare SMSC with BSM in the case of $c=2$. The
simultaneous optimization of the average and robust submodular objectives was
also considered by Wei _et al._ (Wei et al., 2015). This work is different
from BSM in two aspects: (1) the objective function is a linear combination of
average and robust objective functions, to which an approximate solution might
be unbounded for each of them; (2) the algorithms are specific for submodular
data partitioning and not directly applicable for submodular maximization.

Balancing Utility and Fairness in ML and Optimization. The problem of
balancing utility and fairness has also been widely considered for many
machine learning and optimization problems other than submodular optimization.
In supervised learning, the utility is typically measured by the difference in
accuracy (Dwork et al., 2012; Mehrabi et al., 2022) or distribution of model
output (Calmon et al., 2017) before and after fairness intervention, and the
fairness is defined by _demographic parity_ (Dwork et al., 2012) or _equal
opportunity_ (Hardt et al., 2016) for different groups. The overall goal is
thus to improve the fairness metrics at little utility expense. In
unsupervised learning, e.g., center-based clustering (Makarychev and Vakilian,
2021; Ghadiri et al., 2021), and optimization, e.g., allocation (Mashiat et
al., 2022) and matching (Esmaeili et al., 2022), similar to BSM, the utility
is the same as for the original (fairness-unaware) problem, and the fairness
is measured by the utilities for different protected groups. Various schemes
have also been proposed to balance both objectives in those problems. However,
although the above works are similar to our work in formulation, their
algorithmic techniques do not apply to BSM, and vice versa, since none of them
is submodular.

##  3\. Problem Statement

In this section, we first introduce the basic notions, then give the formal
definition of _Bicriteria Submodular Maximization_ (BSM), and finally analyze
the theoretical hardness of BSM.

For a positive integer $n$, we use $[n]$ to denote the set of integers
$\\{1,\ldots,n\\}$. Let $V$ be a set of $n$ items indexed by $[n]$ and $U$ be
a set of $m$ users indexed by $[m]$. For each user $u\in[m]$, we define a non-
negative set function $f_{u}:2^{V}\rightarrow\mathbb{R}_{\geq 0}$ to measure
the utility of any subset $S\subseteq V$ of items for user $u$. We assume that
$f_{u}$ is normalized, i.e., $f_{u}(\emptyset)=0$, monotone, i.e.,
$f_{u}(S)\leq f_{u}(T)$ for any $S\subseteq T\subseteq V$, and submodular,
i.e., $f_{u}(S\cup\\{v\\})-f_{u}(S)\geq f_{u}(T\cup\\{v\\})-f_{u}(T)$ for any
$S\subseteq T\subseteq V$ and $v\in V\setminus T$. We define the following
function to measure the utility of a set $S$ for each user in $U$ on _average_
:

(1) $f(S):=\frac{1}{m}\sum_{u\in[m]}f_{u}(S)$

Following existing submodular maximization literature (Nemhauser et al., 1978;
Badanidiyuru et al., 2014), we assume that the value of $f_{u}(S)$ is given by
an oracle in $\mathcal{O}(1)$ time. Hence, the time complexity of computing
$f(S)$ is $\mathcal{O}(m)$.

We consider the case in which the set $U$ of users is partitioned into $c$
(disjoint) demographic groups according to a certain sensitive attribute,
e.g., _gender_ or _race_ , and $U_{i}\subseteq U$ is the set of users from the
$i$-th group for $i\in[c]$. We want to distribute the utilities across groups
fairly to achieve group-level fairness. Specifically, the average utility
function of the $i$-th group is $f_{i}(S):=\frac{1}{m_{i}}\sum_{u\in
U_{i}}f_{u}(S)$, where $m_{i}=\lvert U_{i}\rvert$. Then, the widely adopted
_maximin fairness_ (García-Soriano and Bonchi, 2020, 2021; Tsang et al., 2019;
Fu et al., 2021), which improves the conditions for the _least well-off_ group
by maximizing the minimum average utility for any of the $i$ groups, is used
as the notion of fairness. This leads to the following function for measuring
how fairly the utilities are distributed among groups:

(2) $g(S):=\min_{i\in[c]}f_{i}(S)=\min_{i\in[c]}\frac{1}{m_{i}}\sum_{u\in
U_{i}}f_{u}(S)$

Towards the balance between _utility_ and _fairness_ , we should consider
optimizing both objective functions jointly: on the one hand, we should
maximize $f$ for the effectiveness of the solution; on the other hand, we
should maximize $g$ for the group-level fairness. To achieve both goals, we
generalize a common framework for bicriteria optimization (Ohsaka and
Matsuoka, 2021; Gershtein et al., 2021). Specifically, the first objective,
i.e., maximizing $f$, is considered the primary objective of the new problem.
Meanwhile, the second objective, i.e., maximizing $g$, is modeled as the
constraint of the new problem, where a factor $\tau\in[0,1]$ is used to
restrict that the function value of $g$ must be at least $\tau$-fraction of
its optimum to seek the balance between both objectives. We define the
_Bicriteria Submodular Maximization_ (BSM) problem as follows.

###### Problem 1.

[Bicriteria Submodular Maximization] Given an item set $V$, a user set $U$
partitioned into $c$ groups $U_{1},\ldots,U_{c}$ with
$\bigcup_{i=1}^{c}U_{i}=U$ and $U_{i}\cap U_{j}=\emptyset$ for any $i,j\in[c]$
($i\neq j$), two functions $f$ and $g$ in Eqs. 1 and 2, the cardinality
constraint $k\in\mathbb{Z}^{+}$, and the balance factor $\tau\in[0,1]$, return
a set $S^{*}\subseteq V$ such that $\lvert S^{*}\rvert=k$, $f(S^{*})$ is
maximized, and $g(S^{*})\geq\tau\cdot\mathtt{OPT}_{g}$, where
$\mathtt{OPT}_{g}=\max_{S^{\prime}\subseteq V,\lvert
S^{\prime}\rvert=k}g(S^{\prime})$. Formally,

$\displaystyle\max_{S\subseteq V,\lvert S\rvert=k}\;\;$
$\displaystyle\;\;f(S)$ subject to
$\displaystyle\;\;g(S)\geq\tau\cdot\mathtt{OPT}_{g}$

Here, $S^{*}$ is called an $\alpha^{*}$-approximate solution if
$f(S^{*})=\alpha^{*}\cdot\mathtt{OPT}_{f}$ where
$\mathtt{OPT}_{f}=\max_{S\subseteq V,\lvert S\rvert=k}f(S)$. Accordingly,
$\alpha^{*}$ is called the best achievable factor for the BSM instance.

Figure 1. Running example for BSM based on an instance of maximum coverage.

###### Example 3.1.

Let us consider the BSM instance for maximum coverage in Figure 1. It consists
of four items $V=\\{v_{1},\ldots,v_{4}\\}$ and a ground set $U$ of twelve
users divided into two groups $U_{1}=\\{u_{11},\ldots,u_{19}\\}$ and
$U_{2}=\\{u_{21},u_{22},u_{23}\\}$. The sets of users covered by $v_{1}$,
$v_{2}$, $v_{3}$, and $v_{4}$ are $S(v_{1})=\\{u_{11},\ldots,u_{15}\\}$,
$S(v_{2})=\\{u_{16},\ldots,u_{19}\\}$, $S(v_{3})=\\{u_{16},u_{19},$
$u_{21}\\}$, and $S(v_{4})=\\{u_{22},u_{23}\\}$.

The maximum coverage problem with a cardinality constraint $k=2$ aims to
select two items to cover the most number of users. Intuitively, it returns
$S_{12}=\\{v_{1},v_{2}\\}$ since $f(S_{12})=\frac{1}{12}\cdot|S(v_{1})\cup
S(v_{2})|=0.75$ is the largest among all combinations of size-$2$ sets in $V$.
The robust maximum coverage problem with the same constraint $k=2$ aims to
maximize the minimum of average coverage between $U_{1}$ and $U_{2}$. It
alternatively returns $S_{14}=\\{v_{1},v_{4}\\}$ with
$\mathtt{OPT}_{g}=g(S_{14})=\min_{i\in\\{1,2\\}}f_{i}(S_{14})=\min\\{\frac{5}{9},\frac{2}{3}\\}\approx
0.556$. A BSM instance with balance factor $\tau\in[0,1]$ finds a solution $S$
that maximizes $f(S)$ while ensuring that $g(S)\geq\tau\cdot\mathtt{OPT}_{g}$.
When $\tau=0$ (i.e., no constraint on $g$), the same solution $S_{12}$ as the
vanilla maximum coverage problem is returned for BSM; when $0<\tau\leq 0.6$,
$S_{13}=\\{v_{1},v_{3}\\}$ is returned for BSM since
$g(S_{13})=\frac{1}{3}\geq\tau\cdot\mathtt{OPT}_{g}$ and $f(S_{13})=8$ is the
maximum among all size-$2$ sets satisfying the constraint on $g$; when
$0.6<\tau\leq 1$, the solution for BSM becomes $S_{14}$ since it is the
size-$2$ set that has the largest coverage on $U$ and can satisfy the
constraint on $g$.

We next analyze the hardness of BSM. First, when $\tau=0$, BSM is equivalent
to maximizing $f$ subject to a cardinality constraint $k$, which is NP-hard
and cannot be approximated within a factor better than $1-1/e$ (i.e.,
$\alpha^{*}\leq 1-1/e$) unless $P=NP$ (Feige, 1998). Furthermore, when
$\tau=1$, we need to compute the optimum $\mathtt{OPT}_{g}$ for maximizing $g$
with a cardinality constraint $k$ to ensure the satisfaction of the
constraint. This is an instance of _robust submodular maximization_ , which is
generally NP-hard to approximate within any constant factor (Krause et al.,
2008). Due to the intractability of computing $\mathtt{OPT}_{f}$ and
$\mathtt{OPT}_{g}$, we consider a bicriteria approximation scheme for BSM.
Specifically, a set $S$ is called an $(\alpha,\beta)$-approximate solution to
a BSM instance for some factors $\alpha,\beta\in(0,1)$ if
$f(S)\geq\alpha\cdot\mathtt{OPT}_{f}$ and
$g(S)\geq\beta\tau\cdot\mathtt{OPT}_{g}$. Finally, we will show by the
following lemma that the objectives of maximizing $f$ and $g$ might contradict
each other. A BSM instance with any $\tau>0$ and $k\geq 1$ can be
inapproximable within any constant factors $\alpha,\beta>0$ even when
$\mathtt{OPT}_{f}$ and $\mathtt{OPT}_{g}$ are known.

Figure 2. BSM instance for the proof of Lemma 3.2.

###### Lemma 3.2.

For any $\tau>0$ and $k\geq 1$, there exists a BSM instance without any
$(\alpha,\beta)$-approximate solution for constants $\alpha,\beta>0$.

###### Proof.

We construct a BSM instance $\mathcal{I}$ that does not have any
$(\alpha,\beta)$-approximate solution for all constants $\alpha,\beta>0$ as
shown in Figure 2. We first consider the procedure of constructing
$\mathcal{I}$ for the case of $k=1$. We have an item set $V=\\{v_{1},v_{2}\\}$
and a user set $U=\\{u_{1},u_{2},\ldots,u_{m}\\}$ with two groups
$U_{1}=\\{u_{1}\\}$ and $U_{2}=\\{u_{2},\ldots,u_{m}\\}$. Then, the utility
function of $u_{1}$ is defined as

$f_{u_{1}}(S)=\begin{cases}\frac{\alpha(m-1)}{m}\text{, if $v_{1}\in S$}\\\
0\text{, otherwise}\end{cases}$

and the utility function of $u_{j}$ for each $j>1$ is defined as

$f_{u_{j}}(S)=\begin{cases}1\text{, if $v_{2}\in S$}\\\
\frac{\alpha(m-1)}{m}\text{, if $v_{1}\in S$ and $v_{2}\notin S$}\\\ 0\text{,
otherwise.}\end{cases}$

Obviously, $f_{u}$ is monotone and submodular for each $u\in U$. To maximize
$f$ on $\mathcal{I}$ with $k=1$, $S_{2}=\\{v_{2}\\}$ is the optimal solution
and $\mathtt{OPT}_{f}=\frac{1}{m}\sum_{u\in[m]}f_{u}(S_{2})=\frac{m-1}{m}$. To
maximize $g$ on $\mathcal{I}$ with $k=1$, $S_{1}=\\{v_{1}\\}$ is the optimal
solution and $\mathtt{OPT}_{g}=f_{1}(S_{1})=\frac{\alpha(m-1)}{m}$. However,
as $g(S_{2})=f_{1}(S_{2})=0$, the approximation factor $\beta$ of $S_{2}$ on
$g$ for any $\tau>0$ is $0$ and thus $S_{2}$ is a $(1,0)$-approximate
solution. In addition,
$f(S_{1})=\frac{\alpha(m-1)}{m}=\alpha\cdot\mathtt{OPT}_{f}$. Therefore,
$S_{1}$ is a $(\alpha,1)$-approximate solution and the best achievable factor
$\alpha^{*}$ of $\mathcal{I}$ is equal to $\alpha$. Since the value of
$\alpha$ can be arbitrarily small, e.g., $\alpha\leq\frac{1}{m}$, there does
not exist any $(\alpha,\beta)$-approximate solution to $\mathcal{I}$ for
constants $\alpha,\beta>0$ when $k=1$.

We further generalize the above construction procedure to the case of $k>1$.
Specifically, we replicate the above constructed instance $k$ times, denoted
as $\mathcal{I}_{1},\ldots,\mathcal{I}_{k}$. For each $\mathcal{I}_{i}$ where
$i\in[k]$, we have an item set $\\{v_{2i-1},v_{2i}\\}$ and a user set
$\\{u_{im-m+1},\ldots,u_{im}\\}$. Then, we assign the first user $u_{im-m+1}$
to group $U_{i}$ and all remaining users to group $U_{k+1}$. The utility
functions of all users are defined in the same way as in $\mathcal{I}$. For
the new instance $\mathcal{I}^{\prime}$, the sets of items and users are the
unions of the sets of items and users for
$\mathcal{I}_{1},\ldots,\mathcal{I}_{k}$. Then, the optimal solution to
maximizing $f$ with a cardinality constraint $k$ on $\mathcal{I}^{\prime}$ is
$S_{2i}=\\{v_{2i}:i\in[k]\\}$, and the optimal solution to maximizing $g$ with
a cardinality constraint $k$ on $\mathcal{I}^{\prime}$ is
$S_{2i-1}=\\{v_{2i-1}:i\in[k]\\}$. We can see that, for every subset
$S\subseteq V^{\prime}$ with $|S|\leq k$ except $S_{2i-1}$, there must exist
some $i\in[k]$ such that $g(S)=f_{i}(S)=0$. Hence, their approximation ratios
on $g$ all equal $0$. Moreover, the approximation ratio of $S_{2i-1}$ on $f$
is $\frac{f(S_{2i-1})}{f(S_{2i})}=\alpha$. Therefore, $S_{2i-1}$ is a
$(\alpha,1)$-approximate solution and the best achievable factor $\alpha^{*}$
of $\mathcal{I}^{\prime}$ is also equal to $\alpha$. Accordingly, the
inapproximability result holds for arbitrary $k\geq 1$. ∎

Given the above inapproximability result, we will focus on instance-dependent
bicriteria approximation schemes for BSM in the subsequent section.

##  4\. Algorithms

In this section, we propose our algorithms for BSM. Our first algorithm is a
two-stage greedy algorithm that combines the two greedy algorithms for
_submodular maximization_ (Nemhauser et al., 1978) and _submodular cover_
(Wolsey, 1982) (Section 4.1). Our second algorithm converts BSM into the
_submodular cover_ (Wolsey, 1982) problem and adapts the Saturate algorithm
(Krause et al., 2008) to obtain a solution to BSM (Section 4.2). We also
analyze the approximation factors and complexities of both algorithms.

###  4.1. The Two-Stage Greedy Algorithm for BSM

By definition, BSM can be divided into two sub-problems, i.e., computing a
solution $S$ that (1) maximizes $f(S)$ and (2) satisfies the constraint
$g(S)\geq\tau\cdot\mathtt{OPT}_{g}$. Therefore, an intuitive scheme to solve
BSM is first to find a solution for each sub-problem independently and then to
combine both solutions as the BSM solution. The above scheme is feasible in
practice because the prior and latter problems are instances of _submodular
maximization_ and _submodular cover_ , respectively, on which Greedy
algorithms (Nemhauser et al., 1978; Wolsey, 1982) can provide approximate
solutions, despite of their NP-hardness (Feige, 1998). Accordingly, we propose
a two-stage greedy algorithm called BSM-TSGreedy, which first runs the greedy
submodular cover algorithm (Wolsey, 1982) to obtain an initial solution based
on the constraint on $g$ and then uses the greedy submodular maximization
algorithm (Nemhauser et al., 1978) to add items to the initial solution for
maximizing $f$. In this way, the final solution after two stages can not only
approximately satisfy the constraint on $g$ due to the items in the first
stage but also maximizes $f$ with an approximation factor depending on the
number of items added in the second stage, thus achieving an instance-
dependent bicriteria approximation as described in Section 3.

Algorithm 1 BSM-TSGreedy

0: Two functions $f,g:2^{V}\rightarrow\mathbb{R}_{\geq 0}$, balance factor
$\tau\in(0,1)$, solution size $k\in\mathbb{Z}^{+}$

0: Solution $S^{\prime}$ with $\lvert S^{\prime}\rvert=k$ for BSM

1: Run Greedy (Nemhauser et al., 1978) on $f$ to compute $S_{f}$ and
$\mathtt{OPT}^{\prime}_{f}$

2: Run Saturate (Krause et al., 2008) on $g$ to compute $S_{g}$ and
$\mathtt{OPT}^{\prime}_{g}$

3: Initialize $S^{\prime}\leftarrow\emptyset$

4: Define
$g^{\prime}_{\tau}(S):=\frac{1}{c}\sum_{i\in[c]}\min\big{\\{}1,\frac{f_{i}(S)}{\tau\cdot\mathtt{OPT}^{\prime}_{g}}\big{\\}}$

5: while $g^{\prime}_{\tau}(S^{\prime})<1$ and $\lvert S^{\prime}\rvert<k$ do

6: $v^{*}\leftarrow\operatorname*{arg\,max}_{v\in
V}g^{\prime}_{\tau}(S^{\prime}\cup\\{v\\})-g^{\prime}_{\tau}(S^{\prime})$

7: $S^{\prime}\leftarrow S^{\prime}\cup\\{v^{*}\\}$

8: if $\lvert S^{\prime}\rvert=k$ and $g^{\prime}_{\tau}(S^{\prime})<1$ then

9: $S^{\prime}\leftarrow S_{g}$

10: else if $\lvert S^{\prime}\rvert<k$ then

11: for $l\leftarrow 1,\ldots,k$ do

12: Let $v_{f,l}$ be the $l$-th item added to $S_{f}$ by Greedy

13: $S^{\prime}\leftarrow S^{\prime}\cup\\{v_{f,l}\\}$

14: if $\lvert S^{\prime}\rvert=k$ then

15: break

16: return $S^{\prime}$

In particular, the procedure of BSM-TSGreedy is presented in Algorithm 1.
First of all, it calls Greedy (Nemhauser et al., 1978) for SM and Saturate
(Krause et al., 2008) for RSM separately to obtain the approximations
$\mathtt{OPT}^{\prime}_{f}$ and $\mathtt{OPT}^{\prime}_{g}$ for
$\mathtt{OPT}_{f}$ and $\mathtt{OPT}_{g}$, respectively. Then, in the first
stage, a function
$g^{\prime}_{\tau}(S):=\frac{1}{c}\sum_{i\in[c]}\min\big{\\{}1,\frac{f_{i}(S)}{\tau\cdot\mathtt{OPT}^{\prime}_{g}}\big{\\}}$
is defined based on $\tau$ and $\mathtt{OPT}^{\prime}_{g}$. It holds that
$g^{\prime}_{\tau}$ is monotone and submodular because (1)
$\overline{f}(t,S):=\min\\{t,f(S)\\}$ is monotone and submodular for any
constant $t\geq 0$ and monotone submodular function $f$ (Krause and Golovin,
2014) and (2) any nonnegative linear combination of monotone submodular
functions is still monotone and submodular (Krause and Golovin, 2014).
Starting from $S^{\prime}=\emptyset$, the item to maximize $g^{\prime}_{\tau}$
is greedily added to $S^{\prime}$ until $g^{\prime}_{\tau}(S^{\prime})=1$,
i.e., $g(S^{\prime})\geq\tau\cdot\mathtt{OPT}^{\prime}_{g}$ and the constraint
on $g$ is (approximately) satisfied, or $\lvert S^{\prime}\rvert=k$. After
that, if $g^{\prime}_{\tau}(S^{\prime})<1$, the partial solution $S^{\prime}$
will be replaced with $S_{g}$. The purpose of this step is to guarantee that a
size-$k$ solution satisfying $g^{\prime}_{\tau}(S^{\prime})=1$ is provided, as
$g^{\prime}_{\tau}(S_{g})=1$ always holds from the definition of
$g^{\prime}_{\tau}$, in the case that the Greedy algorithm fails to find a
size-$k$ solution $S^{\prime}$ with
$g(S^{\prime})\geq\tau\cdot\mathtt{OPT}^{\prime}_{g}$. Then, it executes the
second stage by further adding the items in the greedy solution $S_{f}$ for
maximizing $f$ to $S^{\prime}$ until $\lvert S^{\prime}\rvert=k$ to increase
the value of $f(S^{\prime})$ as largely as possible. Finally, the solution
$S^{\prime}$ after two stages is returned for BSM.

###### Example 4.1.

We consider how BSM-TSGreedy works on the BSM instance with $k=2$ in Figure 1.
As shown in Example 3.1, it first runs Greedy and Saturate to compute
$S_{f}=\\{v_{1},v_{2}\\}$ with $\mathtt{OPT}^{\prime}_{f}=0.75$ and
$S_{g}=\\{v_{1},v_{4}\\}$ with $\mathtt{OPT}^{\prime}_{g}=5/9\approx 0.556$.
Accordingly,
$g^{\prime}_{\tau}(S):=\frac{1}{2}\big{(}\min\\{1,\frac{9f_{1}(S)}{5\tau}\\}+\min\\{1,\frac{9f_{2}(S)}{5\tau}\\}\big{)}$.
When $\tau=0.2$, it adds $v_{3}$ to $S^{\prime}$ in the first stage since
$g^{\prime}_{0.2}(\\{v_{3}\\})=1$, then includes $v_{1}$ into $S^{\prime}$ in
the second stage because $v_{1}$ is the first item in $S_{f}$, and finally
returns $S^{\prime}=\\{v_{1},v_{3}\\}$ for BSM. When $\tau=0.5$, it also first
adds $v_{3}$ to $S^{\prime}$ since $g^{\prime}_{0.5}(\\{v_{3}\\})=0.9$ is the
largest among all four items. Then, either $v_{1}$ or $v_{2}$ can be added to
$S^{\prime}$ because
$g^{\prime}_{0.5}(\\{v_{1},v_{3}\\})=g^{\prime}_{0.5}(\\{v_{2},v_{3}\\})=1$.
Assuming that $v_{2}$ is added, it will return $S^{\prime}=\\{v_{2},v_{3}\\}$
after the first stage, which is inferior to $S_{13}$ since
$f(S^{\prime})=5<f(S_{13})=8$, though they both satisfy the constraint on $g$.
When $\tau=0.8$, it still first adds $v_{3}$ to $S^{\prime}$ with
$g^{\prime}_{0.8}(\\{v_{3}\\})=0.625$. Then, $g^{\prime}_{0.8}(S^{\prime})<1$
and $|S^{\prime}|=2$ after any remaining item is added to $S^{\prime}$. Thus,
it returns $S^{\prime}=S_{g}=\\{v_{1},v_{4}\\}$ according to Line 8 of
Algorithm 1.

Subsequently, we analyze the approximation factor and time complexity of BSM-
TSGreedy in the following theorem.

###### Theorem 4.2.

Algorithm 1 returns a
$\big{(}1-\exp(-\frac{k^{\prime}}{k}),1-\varepsilon_{g}\big{)}$-approximate
solution $S^{\prime}$ with $\lvert S^{\prime}\rvert=k$ for an instance of BSM
in $\mathcal{O}\big{(}nmk\log(cm)\big{)}$ time, where $k^{\prime}$ is the
number of iterations in the second stage, $\varepsilon_{g}\leq
1-\frac{1}{m}-\frac{\widehat{\mathtt{OPT}_{g}}}{\mathtt{OPT}_{g}}$, and
$\widehat{\mathtt{OPT}_{g}}$ is the optimum of maximizing $g$ with a
cardinality constraint $\mathcal{O}\big{(}k\log^{-1}(cm)\big{)}$.

###### Proof.

First of all, Algorithm 1 either finds a solution $S^{\prime}$ such that
$g^{\prime}_{\tau}(S^{\prime})=1$ and
$g(S^{\prime})\geq\tau\cdot\mathtt{OPT}^{\prime}_{g}$ after the first stage,
or replaces $S^{\prime}$ with $S_{g}$, which always satisfies
$g(S_{g})=\mathtt{OPT}^{\prime}_{g}\geq\tau\cdot\mathtt{OPT}^{\prime}_{g}$.
According to the analysis for Saturate in (Nguyen and Thai, 2021, Thm. 8), we
have
$\mathtt{OPT}^{\prime}_{g}\in[(1-\theta)\cdot\widehat{\mathtt{OPT}_{g}},\mathtt{OPT}_{g}]$
where $\widehat{\mathtt{OPT}_{g}}$ is the optimum of maximizing $g$ with a
cardinality constraint
$\mathcal{O}\big{(}k\log^{-1}(\frac{c}{\theta})\big{)}$. By setting
$\theta=\frac{1}{m}$, we obtain that $\varepsilon_{g}\leq
1-\frac{1}{m}-\frac{\widehat{\mathtt{OPT}_{g}}}{\mathtt{OPT}_{g}}$ and the
approximation factor holds for a cardinality constraint
$\mathcal{O}\big{(}k\log^{-1}(cm)\big{)}$. In the second stage, since the
first $k^{\prime}$ items of $S_{f}$ are added to $S^{\prime}$, by applying the
approximation analysis in (Nemhauser et al., 1978) for $k^{\prime}$ instead of
$k$, it holds that
$f(S^{\prime})\geq(1-\exp(-\frac{k^{\prime}}{k}))\cdot\mathtt{OPT}_{f}$.
Therefore, $S^{\prime}$ is a
$\big{(}1-\exp(-\frac{k^{\prime}}{k}),1-\varepsilon_{g}\big{)}$-approximate
solution of size $k$ for BSM.

Moreover, Greedy and Saturate run in $\mathcal{O}(nmk)$ and
$\mathcal{O}\big{(}nmk$ $\log(cm)\big{)}$ time, respectively. The time
complexity of Greedy for maximizing $g^{\prime}_{\tau}$ is $\mathcal{O}(nmk)$
since it always terminates after $k$ iterations no matter whether
$g^{\prime}_{\tau}(S^{\prime})=1$. Then, adding the first $k^{\prime}$ items
of $S_{f}$ to $S^{\prime}$ takes $\mathcal{O}(k)$ time. Thus, the time
complexity of Algorithm 1 is $\mathcal{O}\big{(}nmk\log(cm)\big{)}$. ∎

###  4.2. The Saturate Algorithm for BSM

The BSM-TSGreedy algorithm has two limitations. First, its approximation
factor might be arbitrarily bad (e.g., dropping to $0$ when $k^{\prime}=0$).
Also, how close its approximation factor is to the best achievable factor
$\alpha^{*}$ is unavailable. Second, as will be shown in Section 5, it suffers
from significant losses in solution quality when the number of items added to
$S^{\prime}$ in the first stage for ensuring $g^{\prime}_{\tau}(S^{\prime})=1$
is equal or close to $k$. To achieve better performance for BSM, we
alternatively consider applying a Lagrangian-like formulation similar to that
for SMSC (Ohsaka and Matsuoka, 2021), which combines the maximization of $f$
and the satisfaction of the constraint on $g$ into a single problem, to
convert BSM into _submodular cover_ (Wolsey, 1982) instances. Then, we run the
Saturate algorithm (Krause et al., 2008) for submodular cover to provide a BSM
solution that not only achieves a bicriteria approximation guarantee
theoretically but also strikes a good balance between $f$ and $g$ empirically.

Next, we present the detailed conversion procedure from BSM to submodular
cover. Let us first consider the decision version of BSM defined as follows.

###### Definition 4.3 (BSM Decision).

For any approximation factor $\alpha\in(0,1)$, determine if a set $S\subseteq
V$ with $\lvert S\rvert=k$ such that $f(S)\geq\alpha\cdot\mathtt{OPT}_{f}$ and
$g(S)\geq\tau\cdot\mathtt{OPT}_{g}$ exists.

If the answer to the BSM Decision problem in Definition 4.3 is _yes_ , then
there must exist an $\alpha$-approximate solution to the BSM instance and vice
versa. Assuming that $\mathtt{OPT}_{f}$ and $\mathtt{OPT}_{g}$ are known, the
BSM decision problem for a given $\alpha\in(0,1)$ can be divided into two sub-
problems: _(i)_ is there a size-$k$ set $S\subseteq V$ such that
$f_{\alpha}(S):=\frac{f(S)}{\alpha\cdot\mathtt{OPT}_{f}}\geq 1$? and _(ii)_ is
there a size-$k$ set $S\subseteq V$ such that
$g_{\tau}(S):=\frac{g(S)}{\tau\cdot\mathtt{OPT}_{g}}\geq 1$? The BSM decision
problem is thus transformed to decide whether the objective value of the
following problem equals $2$:

(3) $\max_{S\subseteq V,\lvert
S\rvert=k}\min\\{1,f_{\alpha}(S)\\}+\min\\{1,g_{\tau}(S)\\}.$

Then, the problem of Eq. 3 is reduced to _submodular maximization_ according
to the truncation method as used in (Krause et al., 2008):

(4) $\max_{S\subseteq V,\lvert
S\rvert=k}F_{\alpha}(S):=\min\big{\\{}1,\frac{f(S)}{\alpha\mathtt{OPT}_{f}}\big{\\}}+\frac{1}{c}\sum_{i\in[c]}\min\big{\\{}1,\frac{f_{i}(S)}{\tau\mathtt{OPT}_{g}}\big{\\}}.$

Intuitively, $F_{\alpha}$ in Eq. 4 is monotone and submodular because it is a
nonnegative linear combination of monotone submodular functions. Since
computing the optimums $\mathtt{OPT}_{f}$ and $\mathtt{OPT}_{g}$ is NP-hard,
we further consider replacing them with approximate values
$\mathtt{OPT}^{\prime}_{f}$ and $\mathtt{OPT}^{\prime}_{g}$, i.e.,
$\mathtt{OPT}^{\prime}_{f}\in[(1-\varepsilon_{f})\cdot\mathtt{OPT}_{f},\mathtt{OPT}_{f}]$
and
$\mathtt{OPT}^{\prime}_{g}\in[(1-\varepsilon_{g})\cdot\mathtt{OPT}_{g},\mathtt{OPT}_{g}]$,
where $\varepsilon_{f}$ and $\varepsilon_{g}$ are the relative errors for
approximating $\mathtt{OPT}_{f}$ and $\mathtt{OPT}_{g}$, respectively. The
following lemma indicates that the BSM decision problem will still be answered
with a theoretical guarantee by solving the approximate version of the problem
in Eq. 4.

###### Lemma 4.4.

Let
$F^{\prime}_{\alpha}(S):=\min\big{\\{}1,\frac{f(S)}{\alpha\cdot\mathtt{OPT}^{\prime}_{f}}\big{\\}}+\frac{1}{c}\sum_{i\in[c]}\min\big{\\{}1,$
$\frac{f_{i}(S)}{\tau\cdot\mathtt{OPT}^{\prime}_{g}}\big{\\}}$. On the one
hand, any set $\widehat{S}$ with $F^{\prime}_{\alpha}(\widehat{S})\geq
2(1-\frac{\varepsilon}{c})$ is an $(\hat{\alpha},\hat{\beta})$-approximate
solution to BSM, where $\hat{\alpha}=(1-2\varepsilon-\varepsilon_{f})\alpha$
and $\hat{\beta}=1-2\varepsilon-\varepsilon_{g}$. On the other hand, there is
not any $\alpha$-approximate solution to BSM if $F^{\prime}_{\alpha}(S)<2$ for
any size-$k$ set $S$.

###### Proof.

On the one hand, if $F^{\prime}_{\alpha}(\widehat{S})\geq
2(1-\frac{\varepsilon}{c})$, then it will hold that
$\frac{f(\widehat{S})}{\alpha\cdot\mathtt{OPT}^{\prime}_{f}}\geq
1-\frac{2\varepsilon}{c}$ and
$\frac{1}{c}\sum_{i\in[c]}\frac{f_{i}(\widehat{S})}{\tau\cdot\mathtt{OPT}^{\prime}_{g}}\geq
1-\frac{2\varepsilon}{c}$. According to the prior inequality, we have

$\displaystyle f(\widehat{S})$
$\displaystyle\geq\alpha(1-\frac{2\varepsilon}{c})\cdot\mathtt{OPT}^{\prime}_{f}$
$\displaystyle\geq\alpha(1-2\varepsilon)(1-\varepsilon_{f})\cdot\mathtt{OPT}_{f}$
$\displaystyle>(1-2\varepsilon-\varepsilon_{f})\alpha\cdot\mathtt{OPT}_{f}$

According to the latter inequality, for each $i\in[c]$,

$\displaystyle f_{i}(\widehat{S})$
$\displaystyle\geq\tau\big{(}(1-\frac{2\varepsilon}{c})c-(c-1)\big{)}\cdot\mathtt{OPT}^{\prime}_{g}$
$\displaystyle>\tau(1-2\varepsilon)(1-\varepsilon_{g})\cdot\mathtt{OPT}_{g}$
$\displaystyle>(1-2\varepsilon-\varepsilon_{g})\tau\cdot\mathtt{OPT}_{g}$

Thus,
$g(\widehat{S})=\min_{i\in[c]}f_{i}(\widehat{S})>(1-2\varepsilon-\varepsilon_{g})\tau\cdot\mathtt{OPT}_{g}$.
We prove that $\widehat{S}$ is an $(\hat{\alpha},\hat{\beta})$-approximate
solution to BSM, where $\hat{\alpha}=(1-2\varepsilon-\varepsilon_{f})\alpha$
and $\hat{\beta}=1-2\varepsilon-\varepsilon_{g}$. On the other hand, if
$F^{\prime}_{\alpha}(S)<2$ for any size-$k$ set $S\subseteq V$, then either
$f(S)<\alpha\cdot\mathtt{OPT}^{\prime}_{f}$ or there exists some $i\in[c]$
such that $f_{i}(S)<\tau\cdot\mathtt{OPT}^{\prime}_{g}$ and thus
$g(S)<\tau\cdot\mathtt{OPT}^{\prime}_{g}$. In either case, it must hold that
$f(S)<\alpha\cdot\mathtt{OPT}^{\prime}_{f}<\alpha\cdot\mathtt{OPT}_{f}$ or
$g(S)<\tau\cdot\mathtt{OPT}^{\prime}_{g}<\tau\cdot\mathtt{OPT}_{g}$.
Therefore, $S$ must not be an $\alpha$-approximate solution to BSM. ∎

Algorithm 2 BSM-Saturate

0: Two functions $f,g:2^{V}\rightarrow\mathbb{R}_{\geq 0}$, balance factor
$\tau\in(0,1)$, solution size $k\in\mathbb{Z}^{+}$, error parameter
$\varepsilon\in(0,1)$

0: Solution $\widehat{S}$ with $\lvert\widehat{S}\rvert\leq
k\ln{\frac{c}{\varepsilon}}$ for BSM

1: Run Greedy (Nemhauser et al., 1978) on $f$ to compute
$\mathtt{OPT}^{\prime}_{f}$

2: Run Saturate (Krause et al., 2008) on $g$ to compute
$\mathtt{OPT}^{\prime}_{g}$

3: $\alpha_{max}\leftarrow 1$ and $\alpha_{min}\leftarrow 0$

4: while $(1-\varepsilon)\alpha_{max}>\alpha_{min}$ do

5: Set $\alpha\leftarrow(\alpha_{max}+\alpha_{min})/2$

6: Define
$F^{\prime}_{\alpha}:=\min\big{\\{}1,\frac{f(S)}{\alpha\cdot\mathtt{OPT}^{\prime}_{f}}\big{\\}}+\frac{1}{c}\sum_{i\in[c]}\min\big{\\{}1,$
$\frac{f_{i}(S)}{\tau\cdot\mathtt{OPT}^{\prime}_{g}}\big{\\}}$

7: Initialize $S\leftarrow\emptyset$

8: for $i\leftarrow 1,\ldots,k\ln{\frac{c}{\varepsilon}}$ do

9: $v^{*}\leftarrow\operatorname*{arg\,max}_{v\in
V}F^{\prime}_{\alpha}(S\cup\\{v\\})-F^{\prime}_{\alpha}(S)$

10: $S\leftarrow S\cup\\{v^{*}\\}$

11: if $F^{\prime}_{\alpha}(S)\geq 2(1-\frac{\varepsilon}{c})$ then

12: $\alpha_{min}\leftarrow\alpha$ and $\widehat{S}\leftarrow S$

13: else

14: $\alpha_{max}\leftarrow\alpha$

15: return $\widehat{S}$

Based on Lemma 4.4, we complete the conversion by connecting a BSM decision
problem with a submodular cover problem on $F^{\prime}_{\alpha}$. Accordingly,
we propose BSM-Saturate in Algorithm 2 by solving submodular cover instances
on $F^{\prime}_{\alpha}$ with different $\alpha$’s to find an appropriate
$\alpha$ value and thus provide a good BSM solution. First, it also utilizes
Greedy (Nemhauser et al., 1978) for SM and Saturate (Krause et al., 2008) for
RSM to compute the approximate values $\mathtt{OPT}^{\prime}_{f}$ and
$\mathtt{OPT}^{\prime}_{g}$ for $\mathtt{OPT}_{f}$ and $\mathtt{OPT}_{g}$,
respectively. Next, it performs a bisection search on $\alpha$ within $[0,1]$.
For each value of $\alpha$, it runs Greedy (Nemhauser et al., 1978) to
maximize the submodular function $F^{\prime}_{\alpha}$ defined in Lemma 4.4
with size constraint $k\ln{\frac{c}{\varepsilon}}$. If the function value
$F^{\prime}_{\alpha}(S)$ of the greedy solution $S$ reaches
$2(1-\frac{\varepsilon}{c})$, it will set $S$ as the current solution
$\widehat{S}$ and search on the upper half to find a better solution.
Otherwise, the search will be performed on the lower half to find a feasible
solution. Finally, it terminates the bisection search when the ratio between
the upper and lower bounds of $\alpha$ is within $1-\varepsilon$ and returns
the solution $\widehat{S}$ obtained for the lower bound of $\alpha$ at the
last iteration for BSM.

Subsequently, we analyze the approximation factor and time complexity of BSM-
Saturate in the following theorem.

###### Theorem 4.5.

Algorithm 2 returns a
$\big{(}(1-3\varepsilon-\varepsilon_{f})\alpha^{*},1-2\varepsilon-\varepsilon_{g}\big{)}$-approximate
solution $\widehat{S}$ with $\lvert\widehat{S}\rvert\leq
k\ln{\frac{c}{\varepsilon}}$ for an instance of BSM in
$\mathcal{O}\big{(}nmk\log^{2}(\frac{cm}{\alpha^{*}\varepsilon})\big{)}$ time,
where $\alpha^{*}$ is the best possible approximation factor of the BSM
instance, $\varepsilon_{f}\leq\frac{1}{e}$, $\varepsilon_{g}\leq
1-\frac{1}{m}-\frac{\widehat{\mathtt{OPT}_{g}}}{\mathtt{OPT}_{g}}$, and
$\widehat{\mathtt{OPT}_{g}}$ is the optimum of maximizing $g$ with a
cardinality constraint $\mathcal{O}\big{(}k\log^{-1}(cm)\big{)}$.

###### Proof.

First, since the approximation factor of Greedy (Nemhauser et al., 1978) for
SM is $1-1/e$, we have
$\mathtt{OPT}^{\prime}_{f}\in[(1-1/e)\cdot\mathtt{OPT}_{f},\mathtt{OPT}_{f}]$
and thus $\varepsilon_{f}\leq\frac{1}{e}$. Second, according to the analysis
of Saturate in (Nguyen and Thai, 2021), we have
$\mathtt{OPT}^{\prime}_{g}\in[(1-\frac{1}{m})\cdot\widehat{\mathtt{OPT}_{g}},\mathtt{OPT}_{g}]$
where $\widehat{\mathtt{OPT}_{g}}$ is the optimum of maximizing $g$ with a
cardinality constraint $\mathcal{O}\big{(}k\log^{-1}(cm)\big{)}$. And thus,
$\varepsilon_{g}\leq
1-\frac{1}{m}-\frac{\widehat{\mathtt{OPT}_{g}}}{\mathtt{OPT}_{g}}$. For the
lower bound $\alpha_{min}$ of $\alpha$ when the bisection search in Algorithm
2 is terminated, as it holds that $F^{\prime}_{\alpha_{min}}(\widehat{S})\geq
2(1-\frac{\varepsilon}{c})$, we have $\widehat{S}$ is an
$\big{(}(1-2\varepsilon-\varepsilon_{f})\alpha_{min},1-2\varepsilon-\varepsilon_{g}\big{)}$-approximate
solution to BSM according to Lemma 4.4. Furthermore, for the upper bound
$\alpha_{max}$ of $\alpha$ when the bisection search in Algorithm 2 is
terminated, it holds that
$F^{\prime}_{\alpha_{max}}(S_{\alpha_{max}})<2(1-\frac{\varepsilon}{c})<2$,
where $S_{\alpha_{max}}$ is the greedy solution of size
$k\ln{\frac{c}{\varepsilon}}$ for maximizing $F^{\prime}_{\alpha_{max}}$. By
generalizing the analysis of Greedy in (Nemhauser et al., 1978), for any
monotone submodular function $F$, the greedy solution $S_{l}$ after $l$
iterations satisfies that
$F(S_{l})\geq\big{(}1-\exp(-\frac{l}{k})\big{)}\cdot\mathtt{OPT}_{F}$, where
$\mathtt{OPT}_{F}$ is the optimum of maximizing $F$ with a size constraint
$k$. Taking the above inequality into $F^{\prime}_{\alpha_{max}}$ and
$S_{\alpha_{max}}$, we have

$F^{\prime}_{\alpha_{max}}(S_{\alpha_{max}})\geq\Big{(}1-\exp(-\frac{k\ln{\frac{c}{\varepsilon}}}{k})\Big{)}\cdot\mathtt{OPT}_{F^{\prime}}\geq(1-\frac{\varepsilon}{c})\cdot\mathtt{OPT}_{F^{\prime}}.$

Therefore, we have $\mathtt{OPT}_{F^{\prime}}<2$, i.e.,
$F^{\prime}_{\alpha_{max}}(S)<2$ for any size-$k$ set $S\subseteq V$. Then, we
can safely say there is no $\alpha_{max}$-approximate solution to the BSM
instance and $\alpha^{*}\leq\alpha_{max}$. Considering all the above results,
we prove that $\widehat{S}$ returned by Algorithm 2 is an
$\big{(}(1-3\varepsilon-\varepsilon_{f})\alpha^{*},1-2\varepsilon-\varepsilon_{g}\big{)}$-approximate
solution of size at most $k\ln{\frac{c}{\varepsilon}}$ to any BSM instance.

In terms of complexity, Greedy and Saturate take $\mathcal{O}(nmk)$ and
$\mathcal{O}\big{(}nmk\log(cm)\big{)}$ time, respectively. Moreover, the
bisection search attempts
$\mathcal{O}\big{(}\log(\frac{1}{\alpha^{*}\varepsilon})\big{)}$ different
$\alpha$’s before termination. For each value of $\alpha$, it takes
$\mathcal{O}(nmk\log{\frac{c}{\varepsilon}})$ time to compute a solution $S$.
Therefore, the time complexity of Algorithm 2 is
$\mathcal{O}\big{(}nmk\log^{2}(\frac{cm}{\alpha^{*}\varepsilon})\big{)}$. ∎

Theorem 4.5 indicates that BSM-Saturate improves upon BSM-TSGreedy with better
theoretical guarantees: its approximation factor is close to the best
achievable $\alpha^{*}$ when the error terms are ignored. However, such an
improvement comes at the expense of providing solutions of sizes greater than
$k$. In practice, to ensure that the solution size is at most $k$, we
substitute $k\ln{\frac{c}{\varepsilon}}$ in Line 8 of Algorithm 2 with $k$,
while keeping the remaining steps unchanged.

###### Example 4.6.

We consider running BSM-Saturate on the BSM instance with $k=2$ in Figure 1.
Here, we set $\varepsilon=0.1$ and replace
$k\ln{\frac{c}{\varepsilon}}=2\ln{20}$ in Line 8 with $k=2$ to ensure that the
size of $\widehat{S}$ is $2$. As shown in Example 3.1, it first runs Greedy
and Saturate to compute $S_{f}=\\{v_{1},v_{2}\\}$ with
$\mathtt{OPT}^{\prime}_{f}=0.75$ and $S_{g}=\\{v_{1},v_{4}\\}$ with
$\mathtt{OPT}^{\prime}_{g}\approx 0.556$. For a given $\tau\in[0,1]$, it
maximizes $F^{\prime}_{\alpha}$ in Lemma 4.4 for different $\alpha$’s using
the greedy algorithm until $\frac{\alpha_{min}}{\alpha_{max}}>0.9$ and returns
the solution w.r.t. $\alpha_{min}$ for BSM. When $\tau=0.2$ and $0.5$, it
attempts to maximize $F^{\prime}_{\alpha}$ for $\alpha=0.5$, $0.75$, $0.875$,
and $0.9375$ one by one. For each $\alpha$ value, it adds $v_{3}$ and $v_{1}$
into $S$ and gets $F^{\prime}_{\alpha}(\\{v_{1},v_{3}\\})>1.9$. Thus, it
terminates with $\alpha_{min}=0.9375$, $\alpha_{max}=1$, and
$F^{\prime}_{0.9375}(\\{v_{1},v_{3}\\})\approx 0.95+1>1.9$, and returns
$\widehat{S}=\\{v_{1},v_{3}\\}$ for BSM. When $\tau=0.8$, it also attempts to
maximize $F^{\prime}_{\alpha}$ for $\alpha=0.5$, $0.75$, and $0.875$. However,
it obtains $F^{\prime}_{0.875}(\\{v_{1},v_{3}\\})=1.875<1.9$ for
$\alpha=0.875$. Next, it sets $\alpha=0.8125$ and gets
$F^{\prime}_{0.8125}(\\{v_{1},v_{4}\\})\approx 0.96+1>1.9$. Thus, it finishes
with $\alpha_{min}=0.8125$, $\alpha_{max}=0.875$, and returns
$\widehat{S}=\\{v_{1},v_{4}\\}$ for BSM.

##  5\. Experimental Evaluation

In this section, we evaluate our optimization framework, i.e., BSM, and
algorithms, i.e., BSM-TSGreedy and BSM-Saturate, by extensive experiments on
three problems, namely _maximum coverage_ , _influence maximization_ , and
_facility location_ , using real-world and synthetic datasets. The goal of the
experiments is to answer the following questions:

Q1::

How does the factor $\tau$ affect the balance between the values of two
objective functions $f$ and $g$?

Q2::

How far are the solutions produced by the proposed approximation algorithms
from optimal in practice?

Q3::

How effective and efficient are the proposed algorithms?

Q4::

Are the proposed algorithms scalable to large data?

Algorithms and Baselines. The following algorithms and baselines are compared
in the experiments.

  * •

Greedy (Nemhauser et al., 1978): The classic $(1-1/e)$-approximation greedy
algorithm for SM, which is also used as a subroutine to maximize $f$ in our
algorithms.

  * •

Saturate (Krause et al., 2008): The bicriteria approximation algorithm for
RSM, which is also used as a subroutine to maximize $g$ in our algorithms.

  * •

SMSC (Ohsaka and Matsuoka, 2021): The $(0.16,0.16)$-approximation algorithm
for submodular maximization under submodular cover, which can be used for BSM
only when $c=2$ by maximizing two submodular functions $f_{1}$ and $f_{2}$
simultaneously.

  * •

BSM-Optimal: The exponential-time exact algorithm for BSM. Since the _maximum
coverage_ and _facility location_ problems can be formulated as integer linear
programs (ILPs) (Wolsey, 2020), we find the optimal solutions of small BSM
instances using an ILP solver (see Appendix A). We aim to measure the gap
between the optimal and approximate solutions to BSM.

  * •

BSM-TSGreedy: Our first instance-dependent bicriteria approximation algorithm
for BSM (Algorithm 1).

  * •

BSM-Saturate: Our second instance-dependent bicriteria approximation algorithm
for BSM (Algorithm 2), which is adapted to provide solutions of size at most
$k$ for a fair comparison. In preliminary experiments, we observe that the
value of $\varepsilon$ hardly affects the performance of BSM-Saturate unless
$\varepsilon\geq 0.5$ (see Appendix B). To guarantee the good performance of
BSM-Saturate in all cases, we set $\varepsilon=0.05$ throughout the
experiments in this section.

We implemented all the above algorithms in Python 3. We used the _lazy-
forward_ strategy (Leskovec et al., 2007) to accelerate all algorithms except
BSM-Optimal (for which the _lazy-forward_ strategy is not applicable). The
Gurobi optimizer111https://www.gurobi.com/products/gurobi-optimizer/ was
applied to solve ILPs in BSM-Optimal. All experiments were run on a server
with an Intel Xeon E5-2650v4 2.2GHz processor and 96GB memory running Ubuntu
18.04 LTS. Our code and data are published on
https://github.com/yhwang1990/code-bsm-release.

Table 1. Statistics of datasets in the MC and IM experiments. Dataset |  $n$ (and $m$) | $\lvert E\rvert$ | Percentage of users from each group
---|---|---|---
RAND ($c=2$) | 500 or 100 | 8,946 or 360 |  [‘$U_{0}$’: 20%, ‘$U_{1}$’: 80%]
RAND ($c=4$) | 500 or 100 | 6,655 or 257 |  [‘$U_{0}$’: 8%, ‘$U_{1}$’: 12%, ‘$U_{2}$’: 20%, ‘$U_{3}$’: 60%]
Facebook (Age, $c=2$) | 1,216 | 42,443 |  [‘$<20$’: 8%, ‘$\geq 20$’: 92%]
Facebook (Age, $c=4$) | 1,216 | 42,443 |  [‘$19$’: 8%, ‘$20$’: 28%, ‘$21$’: 31%, ‘$22$’: 33%]
DBLP (Continent, $c=5$) | 3,980 | 6,966 | [‘Asia’: 21%, ‘Europe’: 23%, ‘North America’: 52%, ‘Oceania’: 3%, ‘South America’: 1%]
Pokec (Gender, $c=2$) | 1,632,803 | 30,622,564 | [‘Female’: 51%, ‘Male’: 49%]
Pokec (Age, $c=6$) | 1,632,803 | 30,622,564 | [‘0–20’: 17%, ‘21–30’: 45%, ‘31–40’: 29%, ‘41–50’: 6%, ‘51–60’: 2%, ‘60+’: 1%]

(a) RAND ($c=2,k=5$)

(b) RAND ($c=4,k=5$)

(c) DBLP ($c=5,k=10$)

Figure 3. Results of different algorithms for maximum coverage by varying the
factor $\tau$ on two random graphs and DBLP. The green straight lines in the
plots for $g(S)$ denote $\tau\cdot\mathtt{OPT}_{g}$ (solid) and
$\tau\cdot\mathtt{OPT}^{\prime}_{g}$ (dashed), where $\mathtt{OPT}_{g}$ and
$\mathtt{OPT}^{\prime}_{g}$ are computed by ILP and Saturate, to show whether
the constraints $g(S)\geq\tau\cdot\mathtt{OPT}_{g}$ and
$g(S)\geq\tau\cdot\mathtt{OPT}^{\prime}_{g}$ are satisfied.

###  5.1. Maximum Coverage

Setup. We first apply the BSM framework to the maximum coverage (MC) problem
to maximize the overall coverage while ensuring group-level fairness.
Specifically, for a set $U$ of $m$ users and a collection $V$ of $n$ sets
defined on $U$, we suppose that the utility $f_{u}(S)$ of a set $S\subseteq V$
to user $u$ is equal to $1$ if $u$ is contained by the union of the sets in
$S$ and $0$ otherwise. Given the definition of $f_{u}$, the function $f(S)$ in
Eq. 1 captures the average coverage of $S$ over $U$ and the function $g(S)$ in
Eq. 2 denotes the minimum of average coverages of $S$ among different groups
on $U$.

(a) Facebook (Age, $c=2,\tau=0.8$)

(b) Facebook (Age, $c=4,\tau=0.8$)

(c) Pokec (Gender, $c=2,\tau=0.8$)

(d) Pokec (Age, $c=6,\tau=0.8$)

Figure 4. Results of different algorithms for maximum coverage by varying
solution size $k$ on Facebook and Pokec. The green dashed lines in the plots
for $g(S)$ denote $\tau\cdot\mathtt{OPT}^{\prime}_{g}$, where
$\mathtt{OPT}^{\prime}_{g}$ is computed by Saturate, to indicate whether
$g(S)\geq\tau\cdot\mathtt{OPT}^{\prime}_{g}$.

(a) RAND ($c=2,k=5$)

(b) RAND ($c=4,k=5$)

(c) DBLP ($c=5,k=10$)

Figure 5. Results of different algorithms for influence maximization by
varying the factor $\tau$ on two random graphs and DBLP. The green, dashed
straight lines denote $\tau\cdot\mathtt{OPT}^{\prime}_{g}$, where
$\mathtt{OPT}^{\prime}_{g}$ is computed by Saturate, to show whether
$g(S)\geq\tau\cdot\mathtt{OPT}^{\prime}_{g}$.

We use two synthetic and three real-world datasets in the MC experiments. The
two synthetic datasets are undirected random graphs generated by the
stochastic block model (Holland et al., 1983) (SBM) with 500 nodes consisting
of two and four groups, respectively. We set the intra-group and inter-group
connection probabilities in the generation procedure to $0.1$ and $0.02$. We
also use three publicly available real-world datasets, namely _Facebook_
(Mislove et al., 2010), _DBLP_ (Dong et al., 2023), and _Pokec_
222https://snap.stanford.edu/data/soc-Pokec.html, in the experiments. The
_Facebook_ dataset is an undirected graph representing the friendships between
students at Rice University on Facebook. Profile data contains the _age_
attribute to divide students into two (i.e., $\text{age}<20$ and
$\text{age}\geq 20$) or four (i.e., $\text{age}=19,20,21,22$) groups. The
_DBLP_ dataset is an undirected graph denoting the co-authorships between
researchers. We divide them into five groups based on which continent (i.e.,
‘Asia’, ‘Europe’, ‘North America’, ‘Oceania’, ‘South America’) their
affiliations are located in. The _Pokec_ dataset is a directed graph
representing the follower-followee relationships of users in a social network
in Slovakia. We use the _gender_ and _age_ information in profile data to
divide users into two and six groups, respectively. Table 1 shows the
statistics of all the above datasets, where $n$ (and $m$) is the number of
nodes (and users) and $|E|$ is the number of edges. We also present the
percentage of users from each group in the population. Following a common
dominating set (Bray and Weisstein, 2023) formulation, we construct a set
system on each graph as follows. First, the ground set $U$ is equal to the set
of nodes. Then, for each node $v$, we create a set $S(v)$ containing all its
out-neighbors $N_{out}(v)$ plus itself. Finally, the set collection $V$
consists of the sets created for all the nodes in the graph. Based on the
construction procedure, the task of BSM is to select a set of $k$ nodes that
not only contain the largest number of users in their neighborhoods but also
ensure at least a minimum average coverage for every group.

Results on Effect of $\tau$. Figure 3 shows the values of $f(S),g(S)$, where
$S$ is the solution returned by each algorithm, for each value of factor
$\tau=\\{0.1,0.2,\ldots,0.9\\}$ on two random graphs when $k=5$ and on _DBLP_
when $k=10$. The results for SMSC are ignored on the datasets with more than
two groups because it does not provide any valid solution when $c>2$. The
optimums $\mathtt{OPT}_{f}$ and $\mathtt{OPT}_{g}$ for solely maximizing $f$
and $g$ as well as their approximations $\mathtt{OPT}^{\prime}_{f}$ and
$\mathtt{OPT}^{\prime}_{g}$ returned by Greedy and Saturate are plotted as
black horizontal lines to illustrate the trade-offs between _utility_ ($f$)
and _fairness_ ($g$) of different algorithms w.r.t. $\tau$. In general, our
BSM framework achieves a good utility-fairness trade-off. On the one hand,
when the value of $\tau$ is close to $0$, $f(S)$ approaches or even reaches
$\mathtt{OPT}_{f}$; on the other hand, when the value of $\tau$ increases,
$f(S)$ decreases but $g(S)$ increases accordingly. In contrast, the SMSC
framework fails to balance two objectives well. Compared with the optimal
solutions returned by BSM-Optimal, the approximate solutions returned by BSM-
Saturate and BSM-TSGreedy have up to $9\%$ and $26\%$ losses in $f(S)$. BSM-
TSGreedy provides lower-quality solutions than BSM-Saturate in terms of $f(S)$
for almost all $\tau$ values on all the three graphs. This is mostly because
the solution of BSM-TSGreedy has contained nearly $k$ items after the first
stage, and the number $k^{\prime}$ of items added in the second stage is thus
close to $0$. Nevertheless, BSM-Saturate achieves better trade-offs between
$f(S)$ and $g(S)$ by combining them into a single objective function. We find
that BSM-Saturate and BSM-TSGreedy provide solutions higher in $f(S)$ than
BSM-Optimal in very few cases. Such results do not challenge the optimality of
BSM-Optimal because BSM-Saturate and BSM-TSGreedy do not provide valid BSM
solutions satisfying the constraint of $g(S)\geq\tau\cdot\mathtt{OPT}_{g}$
(i.e., above the solid green line) in these cases. In fact, the solutions of
both BSM-Saturate and BSM-TSGreedy violate the constraint
$g(S)\geq\tau\cdot\mathtt{OPT}_{g}$ of BSM (i.e., below the solid green line)
in some cases, because $\mathtt{OPT}_{g}$ is unknown to them, but always
satisfy a “weaker” constraint $g(S)\geq\tau\cdot\mathtt{OPT}^{\prime}_{g}$
(i.e., above the dashed green line), since $\mathtt{OPT}^{\prime}_{g}$ is used
as their input.

(a) Facebook (Age, $c=2,\tau=0.8$)

(b) Facebook (Age, $c=4,\tau=0.8$)

(c) Pokec (Gender, $c=2,\tau=0.8$)

(d) Pokec (Age, $c=6,\tau=0.8$)

Figure 6. Results of different algorithms for influence maximization by varying the solution size $k$ on Facebook and Pokec. The green dashed lines denote $\tau\cdot\mathtt{OPT}^{\prime}_{g}$, where $\mathtt{OPT}^{\prime}_{g}$ is computed by Saturate, to show whether $g(S)\geq\tau\cdot\mathtt{OPT}^{\prime}_{g}$. Table 2. Statistics of datasets in the FL experiments. Dataset | $n$ | $m$ | $d$ | Percentage of users from each group
---|---|---|---|---
RAND ($c=2$) | 100 | 100 | 5 |  [‘$U_{0}$’: 15%, ‘$U_{1}$’: 85%]
RAND ($c=3$) | 100 | 100 | 5 |  [‘$U_{0}$’: 5%, ‘$U_{1}$’: 20%, ‘$U_{2}$’: 75%]
Adult-Small (Race, $c=5$) | 100 | 100 | 6 | [‘Amer-Indian-Eskimo’: 1%, ‘Asian-Pac-Islander’: 2%, ‘Black’: 14%, ‘White’: 82%, ‘Others’: 1%]
Adult (Gender, $c=2$) | 1,000 | 1,000 | 6 | [‘Female’: 34%, ‘Male’: 66%]
Adult (Race, $c=5$) | 1,000 | 1,000 | 6 | [‘Amer-Indian-Eskimo’: 1%, ‘Asian-Pac-Islander’: 3%, ‘Black’: 10%, ‘White’: 85%, ‘Others’: 1%]
FourSquare-NYC ($c=1,000$) | 882 | 1,000 | 2 |  [‘$u_{0}$’: 0.1%, …, ‘$u_{999}$’: 0.1%]
FourSquare-TKY ($c=1,000$) | 1,132 | 1,000 | 2 |  [‘$u_{0}$’: 0.1%, …, ‘$u_{999}$’: 0.1%]

Results on Effect of $k$. Figure 4 present the values of $f(S),g(S)$, where
$S$ is the solution returned by each algorithm, and the runtime of each
algorithm for the cardinality constraint $k=\\{5,10,\ldots,50\\}$ on
_Facebook_ and $k=\\{10,20,\ldots,100\\}$ on _Pokec_ with different group
partitions. According to Figure 3, we observe that the solutions of each
algorithm are close to those for solely maximizing $f$ (i.e., SM) when
$\tau\leq 0.5$ and to those for solely maximizing $g$ (i.e., RSM) when
$\tau\geq 0.9$. By following the $80\%$ rule, a common practice in algorithmic
fairness, and distinguishing BSM from SM and RSM, we set the value of $\tau$
to $0.8$ in the experiments to better evaluate the effect of $k$. Since
computing the optimal solutions becomes infeasible on large datasets,
$\mathtt{OPT}_{f}$, $\mathtt{OPT}_{g}$, and BSM-Optimal are omitted. In
addition, the runtime of Greedy and Saturate are not presented separately in
Figure 4 since they are used as subroutines in BSM-TSGreedy and BSM-Saturate.
Generally, the values of $f(S)$ and $g(S)$ increase with $k$ for all
algorithms. Meanwhile, the runtime of each algorithm only slightly grows with
$k$. This is because a great number of function evaluations are reduced by
applying the _lazy forward_ strategy, and thus the total number of function
evaluations increases marginally with $k$. BSM-Saturate provides higher-
quality solutions than BSM-TSGreedy at the expense of lower efficiency for
different $k$’s. The solutions of both algorithms satisfy
$g(S)\geq\tau\cdot\mathtt{OPT}^{\prime}_{g}$ in all cases. Finally, their time
efficiencies on _Pokec_ confirm that they are scalable to large graphs with
over one million nodes and thirty million edges. We note that the values of
$f(S)$ and $g(S)$ are much smaller on _Pokec_ than on _Facebook_ because
_Pokec_ is larger and sparser, on which only a very small portion of users
($<7\%$) are covered by at most $100$ nodes.

###  5.2. Influence Maximization

Setup. In the BSM framework, we propose a new problem that integrates the
classic IM (Kempe et al., 2003) aimed to maximize the overall influence spread
over all users and the group fairness-aware IM (Tsang et al., 2019; Becker et
al., 2020) aimed to guarantee a balanced influence distribution among groups.
In particular, we are given a graph $G=(V,E,p)$, where $V$ is a set of nodes,
$E$ is a set of edges, and $p:E\rightarrow\mathbb{R}^{+}$ is a function that
assigns a propagation probability to each edge. We follow the _independent
cascade_ (IC) model (Kempe et al., 2003) to describe the diffusion
process333Note that all the algorithms we compare can be trivially extended to
any diffusion model, e.g., _linear threshold_ and _triggering_ models (Kempe
et al., 2003), and parameter settings where the influence spread function is
monotone and submodular. and set $p(e)=0.1$ or $0.01$ for each $e\in E$. We
define $f_{u}(S)=\mathbb{P}_{u}(S)$, where $\mathbb{P}_{u}(S)$ is the
probability that user $u$ is influenced by a set $S\subseteq V$ of seeds under
the IC model. Accordingly, the two functions $f$ and $g$ in Eqs. 1 and 2 are
equivalent to the influence spread function in (Kempe et al., 2003) divided by
the number of users and the maximin welfare function in (Tsang et al., 2019),
respectively. We use a _reverse influence set_ (Borgs et al., 2014) (RIS)
based algorithm called IMM (Tang et al., 2015) for influence spread
estimation. And for any solution $S$, we run Monte-Carlo simulations 10,000
times to estimate $f(S)$ and $g(S)$. The datasets we use in the IM experiments
are almost identical to those in the MC experiments, except that the number of
nodes in random graphs is reduced to $100$.

Results. Figures 5–6 show the results by varying the factor $\tau=\\{0.1,0.2,$
$\ldots,0.9\\}$ on random graphs when $k=5$ and _DBLP_ when $k=10$, as well as
the results by varying the solution size $k=\\{5,10,\ldots,50\\}$ on
_Facebook_ and $k=\\{10,20,\ldots,100\\}$ on _Pokec_ when $\tau=0.8$. For the
IM problem, the optimal solutions are infeasible even on very small graphs
because computing the influence spread under the IC model is $\\#$P-hard (Chen
et al., 2010). Thus, the results of $\mathtt{OPT}_{f}$, $\mathtt{OPT}_{g}$,
and BSM-Optimal are all ignored. Generally, the results for IM exhibit similar
trends to those for MC. Specifically, BSM-Saturate and BSM-TSGreedy strike
better balances between $f$ and $g$ than SMSC. But the solution quality of
BSM-TSGreedy is mostly close to and sometimes higher than that of BSM-Saturate
for IM. Meanwhile, it still runs 1.5–4× faster than BSM-Saturate.
Nevertheless, BSM-TSGreedy breaks the “weak” constraint of
$g(S)\geq\tau\cdot\mathtt{OPT}^{\prime}_{g}$ in a few cases due to the errors
in influence estimations by IMM. Finally, although our algorithms take much
longer for IM than MC, they are still scalable to large graphs such as _Pokec_
, where the computation is always finished within 1,000 seconds.

(a) RAND ($c=2,k=5$)

(b) RAND ($c=3,k=5$)

(c) Adult-Small ($c=5,k=5$)

Figure 7. Results of different algorithms for facility location by varying the
factor $\tau$ on two random datasets and Adult-Small. The green straight lines
are drawn in the same manner as those in Figure 3.

(a) Adult (Gender, $c=2,\tau=0.8$)

(b) Adult (Race, $c=5,\tau=0.8$)

(c) FourSquare-NYC ($c=1000,\tau=0.8$)

(d) FourSquare-TKY ($c=1000,\tau=0.8$)

Figure 8. Results of different algorithms for facility location by varying the
solution size $k$ on Adult and FourSquare. The green dashed lines are drawn in
the same manner as those in Figure 4.

###  5.3. Facility Location

Setup. Facility location (FL) is a general model for different real-world
problems such as _exemplar clustering_ (Badanidiyuru et al., 2014) and _data
summarization_ (Lindgren et al., 2016). For a set $U$ of $m$ users, a set $V$
of $n$ items (facilities), and a nonnegative _benefit matrix_
$B\in\mathbb{R}^{m\times n}$, where $b_{uv}\in B$ denotes the benefit of item
$v$ on user $u$, we define a function $f_{u}(S)=\max_{v\in S}b_{uv}$ to
measure the benefit of set $S$ on user $u$. In this way, the two functions $f$
and $g$ in Eqs. 1 and 2 measures the average utility for all users and the
minimum of the average utilities for all groups, respectively. And the goal of
our BSM framework is to balance both objectives. Suppose that each user $u$ or
item $v$ is represented as a vector $\mathbf{p}_{u}$ or $\mathbf{p}_{v}$ in
$\mathbb{R}^{d}$. We use two standard methods to compute the benefits in the
literature: one is based on the _k-median clustering_ (Badanidiyuru et al.,
2014), i.e.,
$b_{uv}=\max\\{0,\overline{d}-dist(\mathbf{p}_{u},\mathbf{p}_{v})\\}$, where
$dist(\mathbf{p}_{u},\mathbf{p}_{v})$ is the Euclidean distance between
$\mathbf{p}_{u}$ and $\mathbf{p}_{v}$ and $\overline{d}$ is the distance for
normalization; the other is based on the _RBF kernel_ (Lindgren et al., 2016),
i.e., $b_{uv}=e^{-dist(\mathbf{p}_{u},\mathbf{p}_{v})}$.

In the experiments, we use two public real-world datasets, namely _Adult_
444https://archive.ics.uci.edu/ml/datasets/adult and _FourSquare_ (Yang et
al., 2015). The _Adult_ dataset contains socioeconomic records of individuals,
where the _gender_ and _age_ attributes are used for group partitioning. We
randomly sample 100 or 1,000 records as both facilities and users and adopt
RBF for benefit computation. The _FourSquare_ dataset includes check-in data
in New York City and Tokyo. We extract all locations of _medical centers_ as
facilities, randomly sample 1,000 distinct check-in locations as
representatives of users, and adopt the k-median function for benefit
computation. Since user profiles are not available in _FourSquare_ , we treat
each user as a single group with $c=$ 1,000 groups in total. Moreover, we
generate two random 5$d$ datasets of size 100 with 2 and 3 groups, where each
group corresponds to an isotropic Gaussian blob, and RBF is used for benefit
computation. Table 2 presents the statistics of all the above datasets, where
$n$ is the number of facilities, $m$ is the number of users, and $d$ is the
dimension of feature vectors. We also report the percentage of users from each
group in the population.

Results. Figures 7–8 show the results by varying the factor $\tau=\\{0.1,0.2,$
$\ldots,0.9\\}$ on two random datasets and _Adult-Small_ when $k=5$ and the
solution size $k=\\{5,10,\ldots,50\\}$ on _Adult_ and _FourSquare_ when
$\tau=0.8$. The results for FL are also generally similar to those for MC and
IM. BSM-Saturate has considerable advantages over BSM-TSGreedy in terms of
solution quality, whereas BSM-TSGreedy runs much faster than BSM-Saturate. And
they both strike better balances between $f$ and $g$ than SMSC. Finally, their
performance on _FourSquare_ demonstrates that they are capable of providing
high-quality solutions to BSM efficiently when the number $c$ of groups is
large (i.e., up to $c=1,000$).

##  6\. Conclusions and Future Work

In this paper, we studied the problem of balancing utility and fairness in
submodular maximization. We formulated the problem as a bicriteria
optimization problem called BSM. Since BSM generally could not be approximated
within any constant factor, we proposed two instance-dependent approximation
algorithms called BSM-TSGreedy and BSM-Saturate for BSM. We showed the
effectiveness, efficiency, and scalability of our proposed algorithms by
performing extensive experiments on real-world and synthetic data in three
problems: maximum coverage, influence maximization, and facility location.

In future work, despite the inapproximability of BSM, we will explore how to
further improve the approximation factors for BSM by performing problem-
specific analyses and exploiting the correlations between group-specific
utility functions. It would also be interesting to generalize BSM to non-
monotone or weakly submodular functions.

##  Appendix A ILP Formulation

Although BSM is generally inapproximable, for specific classes of BSM
problems, it is possible to find the optimal solution of a small instance by
solving it as an integer linear programming (Wolsey, 2020) (ILP) problem using
any ILP solver. This approach is referred to as the BSM-Optimal algorithm in
the experiments (Section 5). Here, we define the ILP formulations of _maximum
coverage_ and _facility location_ in the context of BSM. Note that these
formulations are problem-specific and cannot be extended to other submodular
maximization problems, such as _influence maximization_.

(a) RAND (MC, $c=2,k=5$)

(b) RAND (MC, $c=4,k=5$)

(c) RAND (IM, $c=2,k=5$)

(d) RAND (FL, $c=2,k=5$)

Figure 9. Results of BSM-Saturate by varying the error parameter $\varepsilon$
on random datasets ($\tau=0.8$).

By adapting the standard ILP formulation of maximum
coverage555https://en.wikipedia.org/wiki/Maximum_coverage_problem, we present
an ILP to maximize the _average coverage_ (i.e., the function $f$ in BSM) on a
universe $U=\\{u_{1},\ldots,u_{m}\\}$ of $m$ elements (users) and a collection
$V=\\{S_{1},\ldots,S_{n}\\}$ of $n$ sets (items) with a cardinality constraint
$k$ as follows:

(5) $\displaystyle\max\quad$ $\displaystyle\quad\sum_{j\in[m]}\frac{y_{j}}{m}$
subject to $\displaystyle\quad\sum_{l\in[n]}x_{l}\leq k$
$\displaystyle\quad\sum_{u_{j}\in S_{l}}x_{l}\geq y_{j}$ $\displaystyle\quad
y_{j}\in\\{0,1\\},\forall j\in[m]$ $\displaystyle\quad
x_{l}\in\\{0,1\\},\forall l\in[n]$

where $x_{l}$ is an indicator of whether set $S_{l}\in V$ is included in $S$
and $y_{j}$ is an indicator of whether user $u_{j}\in U$ is covered by $S$.

Then, we generalize the ILP in Eq. 5 to robust maximum coverage that aims to
maximize the minimum of the average coverage among $c$ groups
$U_{1},\ldots,U_{c}$ (i.e., the function $g$ in BSM). We introduce a new
variable $w$ to denote the value of $g(S)$. As such, the objective of the
generalized ILP is to maximize $w$. Meanwhile, we should incorporate new
constraints on the average coverage of every group so that it does not exceed
$w$ (thus, $w$ is the minimum). In particular, the ILP formulation of _robust
maximum coverage_ is as follows:

(6) $\displaystyle\max\quad$ $\displaystyle\quad w$ subject to
$\displaystyle\quad\sum_{l\in[n]}x_{l}\leq k$
$\displaystyle\quad\sum_{u_{j}\in S_{l}}x_{l}\geq y_{j}$
$\displaystyle\quad\sum_{u_{j}\in U_{i}}\frac{y_{j}}{m_{i}}\geq w,\forall
i\in[c]$ $\displaystyle\quad y_{j}\in\\{0,1\\},\forall j\in[m]$
$\displaystyle\quad x_{l}\in\\{0,1\\},\forall l\in[n]$ $\displaystyle\quad
w\geq 0$

Finally, given the optimal objective value of robust maximum coverage in Eq. 6
as input $\mathtt{OPT}_{g}$, we can define the BSM version of maximum coverage
for a balance parameter $\tau\in[0,1]$ by adding new constraints
$\sum_{u_{j}\in U_{i}}\frac{y_{j}}{m_{i}}\geq\tau\cdot\mathtt{OPT}_{g}$,
$\forall i\in[c]$ to Eq. 5 to ensure that $g(S)\geq\tau\cdot\mathtt{OPT}_{g}$.

Then, for our facility location problem with a benefit matrix
$B=\\{b_{jl}:j\in[m],l\in[n]\\}\in\mathbb{R}^{m\times n}$, we extend the ILP
formulation for capacitated facility
location666https://en.wikipedia.org/wiki/Facility_location_problem as follows:

(7) $\displaystyle\max\quad$
$\displaystyle\quad\sum_{j\in[m]}\sum_{l\in[n]}\frac{b_{jl}y_{jl}}{m}$ subject
to $\displaystyle\quad\sum_{l\in[n]}x_{l}\leq k$
$\displaystyle\quad\sum_{l\in[n]}y_{jl}\leq 1,\forall j\in[m]$
$\displaystyle\quad y_{jl}\leq x_{l},\forall j\in[m],l\in[n]$
$\displaystyle\quad y_{jl}\in\\{0,1\\},\forall j\in[m],l\in[n]$
$\displaystyle\quad x_{l}\in\\{0,1\\},\forall l\in[n]$

Similarly, we can also generalize Eq. 7 to the robust and BSM versions of
facility location by (_i_) changing the objective to $\max w$ and adding the
new constraints $\sum_{u_{j}\in
U_{i}}\sum_{l\in[n]}\frac{b_{jl}y_{jl}}{m_{i}}\geq w,\forall i\in[c]$ and
(_ii_) adding the new constraints $\sum_{u_{j}\in
U_{i}}\sum_{l\in[n]}\frac{b_{jl}y_{jl}}{m_{i}}$
$\geq\tau\cdot\mathtt{OPT}_{g},\forall i\in[c]$, respectively.

(a) Facebook (MC, Age, $c=2,k=5$)

(b) Facebook (MC, Age, $c=4,k=5$)

(c) Facebook (IM, Age, $c=2,k=5$)

(d) Facebook (IM, Age, $c=4,k=5$)

Figure 10. Results for maximum coverage and influence maximization by varying
the factor $\tau$ on Facebook.

(a) DBLP (MC, $c=5,\tau=0.8$)

(b) DBLP (IM, $c=5,\tau=0.8$)

Figure 11. Results for maximum coverage and influence maximization by varying
the solution size $k$ on DBLP.

##  Appendix B Additional Experiments

Effect of Error Parameter $\varepsilon$: We present how the values of $f(S)$
and $g(S)$ of the solution $S$ returned by BSM-Saturate are affected by the
error parameter $\varepsilon\in\\{0.05,0.1,\ldots,0.5\\}$ in Figure 9. In
opposition to our theoretical analysis, we find that the value of
$\varepsilon$ hardly affects the performance of BSM-Saturate until
$\varepsilon\geq 0.5$ in practice. Since the ratio between $\alpha_{max}$ and
$\alpha_{min}$ (see Line 4 of Algorithm 2) is used as the stop condition, BSM-
Saturate will never terminate until $\alpha_{min}>0$. We observe that the
absolute differences between $\alpha_{min}$’s at different iterations are
often small since they are close to $0$. Thus, their corresponding solutions
are close to each other in terms of $f(S)$ and $g(S)$. Therefore, the values
of $\alpha_{min}$, as well as $f(S)$ and $g(S)$, do not change so much for
different $\varepsilon$’s smaller than $0.5$. Nevertheless, to guarantee the
good performance of BSM-Saturate in extreme cases, we use $\varepsilon=0.05$
in all the experiments of Section 5.

More Results on Effects of $\tau$ and $k$: We provide more results on the
effects of $\tau$ and $k$ in Figures 10–11, which further confirms the
superiority of our proposed algorithms.

###### Acknowledgements.

This work was supported by the National Natural Science Foundation of China
under grant number 62202169.

## References

  * (1)
  * Asudeh et al. (2023) Abolfazl Asudeh, Tanya Berger-Wolf, Bhaskar DasGupta, and Anastasios Sidiropoulos. 2023.  Maximizing Coverage While Ensuring Fairness: A Tale of Conflicting Objectives.  _Algorithmica_ 85 (2023), 1287–1331.
  * Asudeh et al. (2019) Abolfazl Asudeh, H. V. Jagadish, Julia Stoyanovich, and Gautam Das. 2019.  Designing Fair Ranking Schemes. In _Proceedings of the 2019 International Conference on Management of Data_ _(SIGMOD ’19)_. Association for Computing Machinery, New York, NY, USA, 1259–1276.
  * Badanidiyuru et al. (2014) Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. 2014.  Streaming Submodular Maximization: Massive Data Summarization on the Fly. In _Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’14)_. Association for Computing Machinery, New York, NY, USA, 671–680.
  * Bai et al. (2016) Wenruo Bai, Rishabh Iyer, Kai Wei, and Jeff Bilmes. 2016.  Algorithms for Optimizing the Ratio of Submodular Functions. In _Proceedings of The 33rd International Conference on Machine Learning_. PMLR, 2751–2759.
  * Bandyapadhyay et al. (2021) Sayan Bandyapadhyay, Aritra Banik, and Sujoy Bhore. 2021.  On Fair Covering and Hitting Problems. In _Graph-Theoretic Concepts in Computer Science – 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers_. Springer, Cham, 39–51.
  * Becker et al. (2020) Ruben Becker, Federico Corò, Gianlorenzo D’Angelo, and Hugo Gilbert. 2020.  Balancing Spreads of Influence in a Social Network.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 34, 01 (2020), 3–10.
  * Borgs et al. (2014) Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. 2014.  Maximizing Social Influence in Nearly Optimal Time. In _Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms_ _(SODA ’14)_. Society for Industrial and Applied Mathematics, 946–957.
  * Bray and Weisstein (2023) Nicolas Bray and Eric W. Weisstein. 2023.  Dominating Set.  https://mathworld.wolfram.com/DominatingSet.html
  * Călinescu et al. (2011) Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. 2011.  Maximizing a Monotone Submodular Function Subject to a Matroid Constraint.  _SIAM J. Comput._ 40, 6 (2011), 1740–1766.
  * Calmon et al. (2017) Flávio P. Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R. Varshney. 2017.  Optimized Pre-Processing for Discrimination Prevention.  _Advances in Neural Information Processing Systems_ 30 (2017), 3992–4001.
  * Chen et al. (2010) Wei Chen, Chi Wang, and Yajun Wang. 2010.  Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks. In _Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’10)_. Association for Computing Machinery, New York, NY, USA, 1029–1038.
  * Cui et al. (2021) Shuang Cui, Kai Han, Tianshuai Zhu, Jing Tang, Benwei Wu, and He Huang. 2021.  Randomized Algorithms for Submodular Function Maximization with a $k$-System Constraint. In _Proceedings of the 38th International Conference on Machine Learning_. PMLR, 2222–2232.
  * Dong et al. (2023) Yushun Dong, Jing Ma, Song Wang, Chen Chen, and Jundong Li. 2023.  Fairness in Graph Mining: A Survey.  _IEEE Trans. Knowl. Data Eng._ PrePrints (2023), 1–22.  https://doi.org/10.1109/TKDE.2023.3265598
  * Dwork et al. (2012) Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012.  Fairness through Awareness. In _Proceedings of the 3rd Innovations in Theoretical Computer Science Conference_ _(ITCS ’12)_. Association for Computing Machinery, New York, NY, USA, 214–226.
  * El Halabi et al. (2020) Marwa El Halabi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakab Tardos, and Jakub M. Tarnawski. 2020.  Fairness in Streaming Submodular Maximization: Algorithms and Hardness.  _Advances in Neural Information Processing Systems_ 33 (2020), 13609–13622.
  * Emelianov et al. (2022) Vitalii Emelianov, Nicolas Gast, Krishna P. Gummadi, and Patrick Loiseau. 2022.  On fair selection in the presence of implicit and differential variance.  _Artif. Intell._ 302 (2022), 103609.
  * Epasto et al. (2017) Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghaddam. 2017.  Submodular Optimization Over Sliding Windows. In _Proceedings of the 26th International Conference on World Wide Web_ _(WWW ’17)_. Association for Computing Machinery, New York, NY, USA, 421–430.
  * Esmaeili et al. (2022) Seyed A. Esmaeili, Sharmila Duppala, Vedant Nanda, Aravind Srinivasan, and John P. Dickerson. 2022.  Rawlsian Fairness in Online Bipartite Matching: Two-Sided, Group, and Individual. In _Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems_ _(AAMAS ’22)_. Association for Computing Machinery, New York, NY, USA, 1583–1585.
  * Feige (1998) Uriel Feige. 1998.  A Threshold of ln _n_ for Approximating Set Cover.  _J. ACM_ 45, 4 (1998), 634–652.
  * Fu et al. (2021) Xiaoyun Fu, Rishabh Rajendra Bhatt, Samik Basu, and Aduri Pavan. 2021.  Multi-Objective Submodular Optimization with Approximate Oracles and Influence Maximization. In _2021 IEEE International Conference on Big Data (Big Data)_. IEEE, 328–334.
  * García-Soriano and Bonchi (2020) David García-Soriano and Francesco Bonchi. 2020.  Fair-by-design matching.  _Data Min. Knowl. Discov._ 34, 5 (2020), 1291–1335.
  * García-Soriano and Bonchi (2021) David García-Soriano and Francesco Bonchi. 2021.  Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_ _(KDD ’21)_. Association for Computing Machinery, New York, NY, USA, 436–446.
  * Gershtein et al. (2021) Shay Gershtein, Tova Milo, and Brit Youngmann. 2021.  Multi-Objective Influence Maximization. In _Proceedings of the 24th International Conference on Extending Database Technology (EDBT ’21)_. OpenProceedings.org, 145–156.
  * Ghadiri et al. (2021) Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala. 2021.  Socially Fair k-Means Clustering. In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ _(FAccT ’21)_. Association for Computing Machinery, New York, NY, USA, 438–448.
  * Hardt et al. (2016) Moritz Hardt, Eric Price, and Nati Srebro. 2016.  Equality of Opportunity in Supervised Learning.  _Advances in Neural Information Processing Systems_ 29 (2016), 3315–3323.
  * Holland et al. (1983) Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. 1983.  Stochastic blockmodels: First steps.  _Soc. Netw._ 5, 2 (1983), 109–137.
  * Iyer and Bilmes (2012) Rishabh K. Iyer and Jeff A. Bilmes. 2012.  Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications. In _Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence_. AUAI Press, 407–417.
  * Iyer and Bilmes (2013) Rishabh K. Iyer and Jeff A. Bilmes. 2013.  Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints.  _Advances in Neural Information Processing Systems_ 26 (2013), 2436–2444.
  * Jagadish et al. (2019) H. V. Jagadish, Francesco Bonchi, Tina Eliassi-Rad, Lise Getoor, Krishna Gummadi, and Julia Stoyanovich. 2019.  The Responsibility Challenge for Data. In _Proceedings of the 2019 International Conference on Management of Data_ _(SIGMOD ’19)_. Association for Computing Machinery, New York, NY, USA, 412–414.
  * Jin et al. (2021) Tianyuan Jin, Yu Yang, Renchi Yang, Jieming Shi, Keke Huang, and Xiaokui Xiao. 2021.  Unconstrained Submodular Maximization with Modular Costs: Tight Approximation and Application to Profit Maximization.  _Proc. VLDB Endow._ 14, 10 (2021), 1756–1768.
  * Kazemi et al. (2018) Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. 2018.  Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints. In _Proceedings of the 35th International Conference on Machine Learning_. PMLR, 2544–2553.
  * Kearns et al. (2017) Michael J. Kearns, Aaron Roth, and Zhiwei Steven Wu. 2017.  Meritocratic Fairness for Cross-Population Selection. In _Proceedings of the 34th International Conference on Machine Learning_. PMLR, 1828–1836.
  * Kempe et al. (2003) David Kempe, Jon Kleinberg, and Éva Tardos. 2003.  Maximizing the Spread of Influence through a Social Network. In _Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’03)_. Association for Computing Machinery, New York, NY, USA, 137–146.
  * Kleinberg et al. (2019) Jon Kleinberg, Jens Ludwig, Sendhil Mullainathan, and Cass R. Sunstein. 2019.  Discrimination in the Age of Algorithms.  _J. Leg. Anal._ 10 (2019), 113–174.
  * Krause and Golovin (2014) Andreas Krause and Daniel Golovin. 2014.  Submodular Function Maximization.  In _Tractability: Practical Approaches to Hard Problems_. Cambridge University Press, Cambridge, UK, 71–104.
  * Krause et al. (2008) Andreas Krause, H. Brendan McMahan, Carlos Guestrin, and Anupam Gupta. 2008.  Robust Submodular Observation Selection.  _J. Mach. Learn. Res._ 9, 12 (2008), 2761–2801.
  * Leskovec et al. (2007) Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne Van Briesen, and Natalie Glance. 2007.  Cost-Effective Outbreak Detection in Networks. In _Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’07)_. Association for Computing Machinery, New York, NY, USA, 420–429.
  * Li et al. (2018) Yuchen Li, Ju Fan, Yanhao Wang, and Kian-Lee Tan. 2018.  Influence Maximization on Social Graphs: A Survey.  _IEEE Trans. Knowl. Data Eng._ 30, 10 (2018), 1852–1872.
  * Lindgren et al. (2016) Erik M. Lindgren, Shanshan Wu, and Alexandros G. Dimakis. 2016.  Leveraging Sparsity for Efficient Submodular Data Summarization.  _Advances in Neural Information Processing Systems_ 29 (2016), 3414–3422.
  * Makarychev and Vakilian (2021) Yury Makarychev and Ali Vakilian. 2021.  Approximation Algorithms for Socially Fair Clustering. In _Proceedings of Thirty-Fourth Conference on Learning Theory_. PMLR, 3246–3264.
  * Mashiat et al. (2022) Tasfia Mashiat, Xavier Gitiaux, Huzefa Rangwala, Patrick Fowler, and Sanmay Das. 2022.  Trade-Offs between Group Fairness Metrics in Societal Resource Allocation. In _Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency_ _(FAccT ’22)_. Association for Computing Machinery, New York, NY, USA, 1095–1105.
  * Mehrabi et al. (2022) Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. 2022.  A Survey on Bias and Fairness in Machine Learning.  _ACM Comput. Surv._ 54, 6, Article 115 (2022), 35 pages.
  * Mirzasoleiman et al. (2016a) Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. 2016a.  Fast Constrained Submodular Maximization: Personalized Data Summarization. In _Proceedings of The 33rd International Conference on Machine Learning_. PMLR, 1358–1367.
  * Mirzasoleiman et al. (2015) Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. 2015.  Lazier Than Lazy Greedy.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 29 (2015), 1812–1818.
  * Mirzasoleiman et al. (2017) Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. 2017.  Deletion-Robust Submodular Maximization: Data Summarization with “the Right to be Forgotten”. In _Proceedings of the 34th International Conference on Machine Learning_. PMLR, 2449–2458.
  * Mirzasoleiman et al. (2016b) Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. 2016b.  Distributed Submodular Maximization.  _J. Mach. Learn. Res._ 17, 235 (2016), 1–44.
  * Mislove et al. (2010) Alan Mislove, Bimal Viswanath, Krishna P. Gummadi, and Peter Druschel. 2010.  You Are Who You Know: Inferring User Profiles in Online Social Networks. In _Proceedings of the Third ACM International Conference on Web Search and Data Mining_ _(WSDM ’10)_. Association for Computing Machinery, New York, NY, USA, 251–260.
  * Monemizadeh (2020) Morteza Monemizadeh. 2020.  Dynamic Submodular Maximization.  _Advances in Neural Information Processing Systems_ 33 (2020), 9806–9817.
  * Nemhauser et al. (1978) George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. 1978.  An analysis of approximations for maximizing submodular set functions - I.  _Math. Program._ 14, 1 (1978), 265–294.
  * Nguyen and Thai (2021) Lan N. Nguyen and My T. Thai. 2021.  Minimum Robust Multi-Submodular Cover for Fairness.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 35, 10 (2021), 9109–9116.
  * Nikolakaki et al. (2021) Sofia Maria Nikolakaki, Alina Ene, and Evimaria Terzi. 2021.  An Efficient Framework for Balancing Submodularity and Cost. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_ _(KDD ’21)_. Association for Computing Machinery, New York, NY, USA, 1256–1266.
  * Ohsaka and Matsuoka (2021) Naoto Ohsaka and Tatsuya Matsuoka. 2021.  Approximation algorithm for submodular maximization under submodular cover. In _Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence_. PMLR, 792–801.
  * Parambath et al. (2018) Shameem Puthiya Parambath, Nishant Vijayakumar, and Sanjay Chawla. 2018.  SAGA: A Submodular Greedy Algorithm for Group Recommendation.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 32 (2018), 3900–3908.
  * Rawls (1971) John Rawls. 1971.  _A Theory of Justice_.  Harvard University Press, Cambridge, MA, USA.
  * Saha and Getoor (2009) Barna Saha and Lise Getoor. 2009.  On Maximum Coverage in the Streaming Model & Application to Multi-topic Blog-Watch. In _Proceedings of the 2009 SIAM International Conference on Data Mining (SDM)_. Society for Industrial and Applied Mathematics, 697–708.
  * Serbos et al. (2017) Dimitris Serbos, Shuyao Qi, Nikos Mamoulis, Evaggelia Pitoura, and Panayiotis Tsaparas. 2017.  Fairness in Package-to-Group Recommendations. In _Proceedings of the 26th International Conference on World Wide Web_ _(WWW ’17)_. Association for Computing Machinery, New York, NY, USA, 371–379.
  * Tang et al. (2021) Jing Tang, Xueyan Tang, Andrew Lim, Kai Han, Chongshou Li, and Junsong Yuan. 2021.  Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint.  _Proc. ACM Meas. Anal. Comput. Syst._ 5, 1, Article 08 (2021), 22 pages.
  * Tang et al. (2015) Youze Tang, Yanchen Shi, and Xiaokui Xiao. 2015.  Influence Maximization in Near-Linear Time: A Martingale Approach. In _Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data_ _(SIGMOD ’15)_. Association for Computing Machinery, New York, NY, USA, 1539–1554.
  * Thejaswi et al. (2021) Suhas Thejaswi, Bruno Ordozgoiti, and Aristides Gionis. 2021.  Diversity-Aware k-median: Clustering with Fair Center Representation. In _Machine Learning and Knowledge Discovery in Databases. Research Track – European Conference, ECML PKDD 2021, Bilbao, Spain, September 13–17, 2021, Proceedings, Part II_. Springer, Cham, 765–780.
  * Torrico et al. (2021) Alfredo Torrico, Mohit Singh, Sebastian Pokutta, Nika Haghtalab, Joseph (Seffi) Naor, and Nima Anari. 2021.  Structured Robust Submodular Maximization: Offline and Online Algorithms.  _INFORMS J. Comput._ 33, 4 (2021), 1590–1607.
  * Tsang et al. (2019) Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. 2019.  Group-Fairness in Influence Maximization. In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_. International Joint Conferences on Artificial Intelligence Organization, 5997–6005.
  * Udwani (2018) Rajan Udwani. 2018.  Multi-objective Maximization of Monotone Submodular Functions with Cardinality Constraint.  _Advances in Neural Information Processing Systems_ 31 (2018), 9513–9524.
  * Wang et al. (2021) Yanhao Wang, Francesco Fabbri, and Michael Mathioudakis. 2021.  Fair and Representative Subset Selection from Data Streams. In _Proceedings of the Web Conference 2021_ _(WWW ’21)_. Association for Computing Machinery, New York, NY, USA, 1340–1350.
  * Wang et al. (2017) Yanhao Wang, Qi Fan, Yuchen Li, and Kian-Lee Tan. 2017.  Real-Time Influence Maximization on Dynamic Social Streams.  _Proc. VLDB Endow._ 10, 7 (2017), 805–816.
  * Wang et al. (2019) Yanhao Wang, Yuchen Li, and Kian-Lee Tan. 2019.  Efficient Representative Subset Selection over Sliding Windows.  _IEEE Trans. Knowl. Data Eng._ 31, 7 (2019), 1327–1340.
  * Wei et al. (2015) Kai Wei, Rishabh K. Iyer, Shengjie Wang, Wenruo Bai, and Jeff A. Bilmes. 2015.  Mixed Robust/Average Submodular Partitioning: Fast Algorithms, Guarantees, and Applications.  _Advances in Neural Information Processing Systems_ 28 (2015), 2233–2241.
  * Wolsey (2020) Laurence Wolsey. 2020.  _Integer Programming, Second Edition_.  John Wiley & Sons, Inc., Hoboken, NJ, USA.
  * Wolsey (1982) Laurence A. Wolsey. 1982.  An analysis of the greedy algorithm for the submodular set covering problem.  _Combinatorica_ 2, 4 (1982), 385–393.
  * Yang et al. (2015) Dingqi Yang, Daqing Zhang, Vincent W. Zheng, and Zhiyong Yu. 2015.  Modeling User Activity Preference by Leveraging User Spatial Temporal Characteristics in LBSNs.  _IEEE Trans. Syst. Man Cybern. Syst._ 45, 1 (2015), 129–142.