  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 \emph{utility} and \emph{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 \emph{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.
