\section{Introduction}
Many well known objectives in combinatorial optimization exhibit two common properties: the marginal value of any given element is non-negative and it decreases as more and more elements are selected. The notions of submodularity and monotonicity \footnote{A set function $f:2^N\rightarrow \mathbb{R}$ on the ground set $N$
	is called submodular when
	$f(A+a)-f(A)\leq f(B+a)-f(B) \text{  for all } B\subseteq A\subseteq N \text{ and } a\in N\setminus A.$. The function is monotone if $f(B)\leq f(A) \text{ for all } B\subseteq A$. W.l.o.g., assume $f(\emptyset)=0$. Combined with monotonicity this implies non-negativity. } nicely capture this property, resulting in the appearance of constrained monotone submodular maximization in a wide and diverse array of modern applications in machine learning and optimization, including feature selection (\cite{motive1,feature1}), network monitoring (\cite{sense3}), news article recommendation (\cite{news}), sensor placement and information gathering (\cite{sense0,sense1,sense2,sense4}), viral marketing and influence maximization (\cite{kempeinflu,influ}), document summarization (\cite{docsum}) and crowd teaching (\cite{crowd}).  

Here we are interested in scenarios where multiple objectives, all monotone submodular, need to be simultaneously maximized subject to a cardinality constraint. This problem has an established line of work in both machine learning \cite{main}  and the theory community \cite{swap}. As an example application, in robust experimental design one often seeks to maximize a function $f_{\theta}$, which is monotone submodular for every value of $\theta$. The function is very sensitive to the choice of $\theta$ but the parameter is unknown a priori and estimated from data. Therefore, one possible approach to finding a robust solution is to maximize the function $min_{\theta\in \Theta} f_{\theta}(.)$, where $\Theta$ is a set that captures the uncertainty in $\theta$. If $\Theta$ is assumed to be a finite set of discrete values \cite{main} we have an instance of multi-objective monotone submodular maximization. More generally, we consider the following problem,
$$MO_1: \max_{A\subseteq N, |A|\leq k}\, 
\min_{i\in\{1,2,\dots,m\}} f_i(A),$$
where $f_i(.)$ is monotone submodular for every $i\in\{1,\dots,m\}$. The problem also has an alternative formulation due to \cite{swap}, which we discuss later. Broadly speaking, there are two ways in which this framework has been applied --

\noindent\textbf{When there are several natural criteria that need to be simultaneously optimized: }such as in network monitoring, sensor placement and information gathering \cite{sense0,sense3,sense4,main}. For example in the problem of intrusion detection \cite{sense0}, one usually wants to maximize the likelihood of detection while also minimizing the time until intrusion is detected, and the population affected by intrusion. The first objective is often monotone submodular and the latter objectives are monotonically decreasing supermodular functions \cite{sense3,sense4}. Therefore, the problem is often formulated as an instance of cardinality constrained maximization with a small number of submodular objectives.  

\noindent \textbf {When looking for solutions robust to the uncertainty in objective: }such as in feature selection \cite{main,ml}, variable selection and experimental design \cite{main}, robust influence maximization \cite{influ}. In these cases, there is often inherently just a single submodular objective which is highly prone to uncertainty either due to dependence on a parameter that is estimated from data, or due to multiple possible scenarios that each give rise to a different objective. Therefore, one often seeks to optimize over the worst case realization of the uncertain objective, resulting in an instance of multi-objective submodular maximization. 

In some applications the number of objectives is given by the problem structure and can be larger even than the cardinality parameter. However, in applications such as robust influence maximization, variable selection and experimental design, the number of objectives is a design choice that trades off optimality with robustness.  



\subsection{Related Work}
The problem of maximizing a monotone submodular function subject to a cardinality constraint, $$P_0:= \max_{A\subseteq N, |A|\leq k} f(A),$$ goes back to the work of \cite{nem,nem1}, where they showed that the greedy algorithm gives a guarantee of $(1-1/e)$ and this is best possible in the value-oracle model. Later, \cite{hard} showed that this is also the best possible approximation unless P=NP. While this settled the hardness and approximability of the problem, finding faster approximations remained an open line of inquiry. Notably, \cite{fast} found a faster algorithm for $P_0$ that improved the quadratic $O(nk)$ query complexity of the classical greedy algorithm to nearly linear complexity, by trading off on the approximation guarantee. This was later improved by \cite{lazyfast}.

For the more general problem $\max_{A\in\mathcal{I}} f(A)$, where $\mathcal{I}$ is the collection of independent sets of a matroid; \cite{vond1,welf} in a breakthrough, achieved a $(1-1/e)$ approximation by (approximately) maximizing the \textit{multilinear extension} of submodular functions, followed by suitable rounding.
Based on this framework, tremendous progress was made over the last decade for a variety of different settings (\cite{vond1,welf,multiuni,hard1,vond,swap}).

In the multi-objective setting, \cite{main} amalgamated various applications and formally introduced the following problem,
$$P_1=\max_{A\subseteq N, |A|\leq k}\, 
\min_{i\in\{1,2,\dots,m\}} f_i(A),$$
where $f_i(.)$ is monotone submodular for every $i$. They call this the Robust Submodular Observation Selection (RSOS) problem and show that in general the problem is inapproximable (no non-trivial approximation possible) unless $P=NP$. Consequently, they proceeded to give a bi-criterion approximation algorithm, called SATURATE, which achieves the optimal answer by violating the cardinality constraint. Note that their inapproximability result only holds when  $m=\Omega(k)$. Another bi-criterion approximation was given more recently in \cite{chen}.

On the other hand, \cite{swap} showed
a randomized $(1-1/e)-\epsilon$ approximation for constant $m$ in the more general case of matroid constraint, as an application of a new technique for rounding over a matroid polytope, called \emph{swap rounding}. The runtime scales as $O(n^{m/\epsilon^3} + mn^8)$ \footnote{\label{runtime}The $n^8$ term could potentially be improved to $n^5$ by leveraging subsequent work \cite{fast,filmus}.}. Note, \cite{swap} consider a different but equivalent formulation of the problem that stems from the influential paper on multi-objective optimization \cite{papad}. The alternative formulation, which we review in Section \ref{prelim}, is the reason we call this a multi-objective maximization problem (same as \cite{swap}). For the special case of cardinality constraint (which will be our focus here), \cite{ipcofull} recently showed that the greedy algorithm can be generalized to achieve a \emph{deterministic} $1-1/e-\epsilon$ approximation for the special case of bi-objective maximization. Their runtime scales as $n^{1+ 1/\epsilon}$ and $\epsilon\leq 1/2$. To the best of our knowledge, when $m=o(k)$ no  constant factor approximation algorithms or inapproximability results were known prior to this work.
\subsection{Our Contributions}
Our focus here is on the regime $m=o(k)$. This setting is essential to understanding the approximability of the problem for super-constant $m$ and includes several of the applications we referred to earlier. For instance, in network monitoring and sensor placement, the number of objectives is usually a small constant \cite{main,sense3}. For robust influence maximization, the number of objectives depends on the underlying uncertainty but is often small \cite{influ}. And in settings like variable selection and experimental design \cite{main}, where the number of objectives considered is a design choice. We show three algorithmic results with asymptotic approximation guarantees for $m=o(k)$. 

\textbf{1. Asymptotically optimal approximation algorithm:} We give a $(1-1/e-\epsilon)(1-\frac{m}{k\epsilon^3})$ approximation, which for $m=o\big(\frac{k}{\log^3 {k}}\big)$ and $\epsilon=\min\{\frac{1}{8\ln m},\sqrt[4]{\frac{m}{k}}\}$ tends to $1-1/e$ as $k\to \infty$. The algorithm is randomized and outputs such an approximation w.h.p. Observe that this implies a steep transition around $m$, due to the inapproximability result (to within any non-trivial factor) for $m=\Omega(k)$. 

We obtain this via extending the matroid based algorithm of \cite{swap}, which relies on the \emph{continuous greedy} approach, resulting in a runtime of $\tilde{O}(mn^8)$. Note that there is no $\epsilon$ dependence in the runtime, unlike the result from \cite{swap}. The key idea behind the result is quite simple, and relies on exploiting the fact that we are dealing with a cardinality constraint, far more structured than matroids.


\textbf{2. Fast and practical approximation algorithm:}
In practice, $n$ can range from tens of thousands to millions (\cite{sense0,sense3}), which makes the above runtime intractable. To this end, we develop a fast $O(\frac{n}{\delta^3}\log m\log \frac{n}{\delta})$ time $(1-1/e)^2(1-m/k\epsilon^3)-\epsilon-\delta$ approximation. Under the same asymptotic conditions as above, the guarantee simplifies to $(1-1/e)^2-\delta$.
We achieve this via the Multiplicative-Weight-Updates (MWU) framework, which replaces the bottleneck continuous greedy process. This is what costs us the additional factor of $(1-1/e)$ in the guarantee but allows us to leverage the runtime improvements for $P_0$ achieved in \cite{fast,lazyfast}. 

MWU has proven to be a vital tool in the past few decades (\cite{mwu1,mwu3,mwu4,mwu8,mwu9,plotkin,arora}). Linear functions and constraints have been the primary setting of interest in these works, but recent applications have shown its usefulness when considering non-linear and in particular submodular objectives (\cite{azar,chekurimwu}). Unlike these recent applications, we instead apply the MWU framework in vein of the Plotkin-Shmoys-Tardos scheme for linear programming (\cite{plotkin}), essentially showing that the non-linearity only costs us a another factor of $(1-1/e)$ in the guarantee and yields a nearly linear time algorithm. Independently and prior to our work, \cite{chen} applied the MWU framework in a similar manner and gave a new bi-criterion approximation. We further discuss how our result differs from theirs in Section \ref{keyfast}.  

\textbf{3. Finding a deterministic approximation for small $m$:}
While the above results are all randomized, we also show a simple greedy based deterministic $1-1/e-\epsilon$ approximation with runtime $kn^{m/\epsilon^4}$. This follows by establishing an upper bound on the increase in optimal solution value as a function of cardinality $k$, which also resolves a weaker version of a conjecture posed in \cite{ipcofull}

\textbf{Outline:} We start with definitions and preliminaries in Section 2, where we also review relevant parts of the algorithm in \cite{swap} that are essential for understanding the results here. In Section 3, we state and prove the main results. Since the guarantees we present are asymptotic and technically converge to the constant factors indicated as $k$ becomes large, in Section 4 we test the performance of a heuristic, closely inspired by our MWU based algorithm, on Kronecker graphs \cite{kron} of various sizes and find improved performance over previous heuristics even for small $k$ and large $m$.

\section{Preliminaries}\label{prelim}
\subsection{Definitions \& review}

We work with a ground set $N$ of $n$ elements and recall that we use $P_0$ to denote the single objective (classical) problem. \cite{nem,nem1} showed that the natural \emph{greedy algorithm} for $P_0$ achieves a guarantee of $1-1/e$ for $P_0$ and that this is best possible. The algorithm can be summarized as follows --

\emph{Starting with $\emptyset$, at each step add to the current set an element which adds the maximum marginal value until $k$ elements are chosen.} 

Formally, given set $A$ the marginal increase in value of function $f$ due to inclusion of set $X$ is, $$f(X|A)=f(A\cup X)-f(A).$$
Let $\beta(\eta)=1-\frac{1}{e^{\eta}}\in [0,1-1/e]$ for $\eta \in[0,1]$. Note that $\beta(1)=(1-1/e)$. Further, for $k'\leq k$, 
\begin{equation}
\beta(k'/k)= (1-e^{1-k'/k}/e)\geq (1-1/e)k'/k. \label{simfact}
\end{equation}
This function appears naturally in our analysis and will be useful for expressing approximation guarantees.



We use the notation $\textbf {x}_S$ for the support vector of a set $S$ (1 along dimension $i$ if $i\in S$ and 0 otherwise). We also use the short hand $|\textbf{x}|$ to denote the $\ell_1$ norm of a vector $\textbf {x}$. Given $f:2^{N}\to \mathbb{R}$, recall that its \emph{multilinear extension} over ${\bf x}=\{x_1,\dots,x_n\}\in [0,1]^{n}$ is defined as, $$F({\bf x})=\sum_{S\subseteq N}f(S)\prod_{i\in S}x_i\prod_{j\not\in S}(1-x_j).$$
The function can also be interpreted as the expectation of function value over sets obtained by including element $i\in N$ independently with probability $x_i, \forall i$. 
$F$ acts as a natural replacement for the original function $f$ in the \emph{continuous greedy algorithm} (\cite{vond1}). Like the greedy algorithm, the \emph{continuous} version always moves in a feasible direction that best increases the value of function $F$. While evaluating the exact value of this function and its gradient is naturally hard in general, for the purpose of using this function in optimization algorithms, approximations obtained using a sampling based oracle suffice (\cite{fast,swap,vond1}). Given two vectors ${\bf x},{\bf y}\in[0,1]^n$, let ${ \bf x}\vee \bf{y}$ denote the component wise maximum. Then we define marginals for $F$ as, $$F({\bf x}|{\bf y})=F({ \bf x}\vee {\bf y})- F({\bf y}).$$ 

Now, we briefly discuss another formulation of the multi-objective maximization problem, call it $P_2$, introduced in \cite{swap}. In $P_2$ we are given a target value $V_i$ (positive real) with each function $f_i$ and the goal is to find a set $S^*$ of size at most $k$, such that $f_i(S^*)\geq V_i,\, \forall i\in\{1,\dots,m\}$ or certify that no $S^*$ exists. More feasibly one aims to efficiently find a set $S$ of size $k$ such that $f_i(S)\geq \alpha V_i$ for all $i$ and some factor $\alpha$, or certify that there is no set $S^*$ of size $k$ such that $f_i(S^*)\geq V_i,\, \forall i$. Observe that w.l.o.g.\ we can assume $V_i=1, \forall i$ (since we can consider functions $f_i(.)/V_i$ instead) and therefore $P_2$ is equivalent to the decision version of $P_1$: \emph{Given $t>0$, find a set $S^*$ of size at most $k$ such that $\min_{i}f_i(S^*)\geq t$, or give a certificate of infeasibility.} 


When considering formulation $P_2$, \emph{since we can always consider the modified submodular objectives $\min\{f_i(.),V_i\}$, we w.l.o.g.\ assume that $f_i(S)\leq V_i$ for every set $S$ and every function $f_i$.} Finally,  for both $P_1,P_2$ we use $S_k$ to denote an optimal/feasible set (optimal for $P_1$, and feasible for $P_2$) to the problem and $OPT_k$ to denote the optimal solution value for formulation $P_1$.
We now give an overview of the algorithm from \cite{swap} which is based on $P_2$. To simplify the description we focus on cardinality constraint, even though it is designed more generally for matroid constraint. We refer to it as \textbf{Algorithm 1} and it has three stages. Recall, the algorithm runs in time $O(n^{m/\epsilon^3}+mn^8)$. 


{\bf Stage 1:}
Intuitively, this is a pre-processing stage with the purpose of picking a small initial set consisting of elements with 'large' marginal values, i.e. marginal value at least $\epsilon^3 V_i$ for some function $f_i$. This is necessary for technical reasons due to the rounding procedure in Stage 3.

Given a set $S$ of size $k$, fix a function $f_i$ and index elements in $S=\{s_1,\dots,s_k\}$ in the order in which the greedy algorithm would pick them. There are at most $1/\epsilon^3$ elements such that $f_i(s_j|\{s_1,\dots,s_{j-1}\})\geq \epsilon^3V_i$, since otherwise by monotonicity $f_i(S)>V_i$ (violating our w.l.o.g.\ assumption that $f_i(S)\leq V_i\, \forall i$). In fact, due to decreasing marginal values we have, $f_i(s_j|\{s_1,\dots,s_{j-1}\})<\epsilon^3V_i$ for every $j>1/\epsilon^3$.

Therefore, we focus on sets of size $\leq m/\epsilon^3$ (at most $1/\epsilon^3$ elements for each function) to find an initial set such that the remaining elements have marginal value $\leq \epsilon^3 V_i$ for $f_i$, for every $i$. In particular, one can try all possible initial sets of this size (i.e. run subsequent stages with different starting sets), leading to the $n^{m/\epsilon^3}$ term in the runtime. Stages 2 and 3 have runtime polynomial in $m$ (in fact Stage $3$ has runtime independent of $m$). Hence, Stage 1 is really the bottleneck. For the more general case of matroid constraint, it is not obvious at all if one can do better than brute force enumeration over all possible starting sets and still retain the approximation guarantee. However, we will show that for cardinality constraints one can easily avoid enumeration. 


{\bf Stage 2:} 
Given a starting set $S$ from stage one, this stage works with the ground set $N-S$ and runs the continuous greedy algorithm. Suppose a feasible set $S_k$ exists for the problem, then for the right starting set $S_1\subset S_k$, this stage outputs a fractional point ${\bf x}(k_1)\in[0,1]^n$ with $|{\bf x}(k_1)|=k_1=k-|S_1|$ such that $F_i({\bf x}(k_1)|{\bf x}_{S_1})\geq (1-1/e) (V_i-f_i(S_1))$ for every $i$.
However, this is computationally expensive and takes time $\tilde{O}(mn^8)$. We formally summarize this stage in the following lemma and refer the interested reader to \cite{swap} for further details (which will not be necessary for subsequent discussion).
\begin{lem}\label{congreedy}
	(\cite{swap} Lemma 7.3) Given submodular functions $f_i$ and values $V_i$, cardinality $k$, the continuous greedy algorithm finds a point ${\bf x}\in[0,1]^{n}$ such that 
	$F_i({\bf x}(k))\geq (1-1/e)V_i, \forall i$ or outputs a certificate of infeasibility.
\end{lem}




{\bf Stage 3:}  For the right starting set $S_1$ (if one exists), Stage 2 successfully outputs a point ${\bf x}(k_1)$.
Stage 3 now follows a random process that converts ${\bf x}(k_1)$ into a set $S_2$ of size $k_1$ such that, $S_2\in N-S_1$ and $f_i(S_1\cup S_2)\geq (1-1/e)(1-\epsilon)V_i, \forall i$ as long as $\epsilon< 1/8\ln m$. The rounding procedure is called \emph{swap rounding} and we include a specialized version of the formal lemma below
\begin{lem}\label{swap}
	(\cite{swap} Theorem 1.4, Theorem 7.2) Given $m$ monotone submodular functions $f_i(.)$ with the maximum value of singletons in $[0,\epsilon^3V_i]$ for every $i$; a fractional point ${\bf x}$ with $|{\bf x}|\in \mathbb{Z}$ and $\epsilon< \frac{1}{8\gamma \ln m}$. Swap Rounding yields a set $R$ with cardinality $|{\bf x}|$, such that,
	$$\sum_i \Pr[f_i(R)<(1-\epsilon)F_i({\bf x})]< me^{-1/8\epsilon}< 1/m^{\gamma-1}.$$
\end{lem}

\emph{Remark:} For any $\gamma> 1$, the above can be converted to a result w.h.p.\ by standard repetition. Also this is a simplified version of the matroid based result in \cite{swap}.
\subsection{Some simple heuristics}\label{standheu}
Before we present the main results, let us take a step back and examine some variants of the standard greedy algorithm. To design a greedy heuristic for multiple functions, what should the objective for greedy selection be?

One possibility is to split the selection of $k$ elements into $m$ equal parts. In part $i$, pick $k/m$ elements greedily w.r.t. function $f_i$. It is not difficult to see that this is a (tight) $\beta(k/m)$ approximation. Second, recall that the convex combination of monotone submodular functions is also monotone and submodular. Therefore, one could run the greedy algorithm on a fixed convex combination of the $m$ functions. It can be shown this does not lead to an approximation better than $1/\Theta(m)$. This is indeed the idea behind the bi-criterion approximation in \cite{main}.   
Third, one could select elements greedily w.r.t. to the objective function $h(.)=\min_i f_i(.)$. A na\"ive implementation of this algorithm can have arbitrarily bad performance even for $m=2$ (previously observed in \cite{ipcofull}). We show later in Section \ref{resolve}, that if one greedily picks sets of size $k'$ instead of singletons at each step, for large enough $k'$ one can get arbitrarily close to $(1-1/e)$.
\section{Main Results}



\subsection{Asymptotic $(1-1/e)$ approximation for $m=o\big(\frac{k}{\log^3 {k}}\big)$}\label{step1}
We replace the enumeration in Stage 1 with a single starting set, obtained by scanning once over the ground set. The main idea is simply that for the cardinality constraint case, any starting set that fulfills the Stage 3 requirement of small marginals will be acceptable (not true for general matroids).

{\bf New Stage 1:}
Start with $S_1=\emptyset$ and pass over all elements once in arbitrary order.
\emph{For each element $e$, add it to $S_1$ if for some $i$, $f_i(e|S_1)\geq \epsilon^3V_i$.} Note that we add at most $m/\epsilon^3$ elements (at most $1/\epsilon^3$ for each function). When the subroutine terminates, for every remaining element $e\in N\backslash S_1$, $f_i(e|S_1)<\epsilon^3V_i, \forall i$ (as required by Lemma \ref{swap}). Let $k_1=k-|S_1|$ and note $k_1\geq k- m/\epsilon^3$.

Stage 2 remains the same as Algorithm 1 and outputs a fractional point ${\bf x}(k_1)$ with $|{\bf x}(k_1)|=k_1$. While enumeration over all starting sets allowed us to find a starting set such that $F_i({\bf x}(k_1)|{\bf x}_{S_1})\geq (1-1/e) (V_i-f_i(S_1))$ for every $i$; with the new Stage 1 we will need to further exploit properties of the multilinear extension to show a similar lower bound on the marginal value of ${\bf x}(k_1)$. \begin{coro}\label{concavity}
	Given a point ${\bf x}\in[0,1]^n$ with $|{\bf x}|=k$ and a multilinear extension $F$ of a monotone submodular function, for every $k_1\leq k$, 
	$$F\Big(\frac{k_1}{k}{\bf x}\Big)\geq \frac{k_1}{k}F({\bf x}).$$
\end{coro}
\begin{proof}{Proof}
	Note that the statement is true for concave $F$. The proof now follows directly from the concavity of multilinear extensions in positive directions (Section 2.1 of \cite{vond1}).
\end{proof}

\begin{lem}\label{stage2}
	$F_i({\bf x}(k_1)|{\bf x}_{S_1})\geq \beta(1)\frac{k_1}{k} (V_i-f_i(S_1))$ for every $i$.
\end{lem}
\begin{proof}{Proof}
	Recall that $S_k$ denotes a feasible solution with cardinality $k$, and let ${\bf x}_{S_k}$ denote its characteristic vector. Clearly, $|{\bf x}_{S_k \backslash S_1}|\leq k$ and $F_i({\bf x}_{S_k \backslash S_1}|{\bf x}_{S_1})=f_i(S_k | S_1)\geq (V_i-f_i(S_1))$ for very $i$. And now from Corollary \ref{concavity}, we have that there exists a point ${\bf x}'$ with $|{\bf x}'|= k_1$ such that $F_i({\bf x}'|{\bf x}_{S_1})\geq\frac{k_1}{k} F_i({\bf x}_{S_k \backslash S_1}|{\bf x}_{S_1})$ for every $i$. Finally, using Lemma \ref{congreedy} we have $F_i({\bf x}(k_1)|{\bf x}_{S_1})\geq \beta(1)F_i({\bf x}'|S_1)$, which gives the desired bound. 
\end{proof}
Stage 3 rounds ${\bf x}(k_1)$ to $S_2$ of size $k_1$, and final output is $S_1\cup S_2$. The following theorem now completes the analysis.





\begin{thm}\label{extension}
	For $\epsilon=\min\{\frac{1}{8\ln m},\sqrt[4]{\frac{m}{k}}\}$ we have, $f_i(S_1\cup S_2)\geq (1-\epsilon)(1-1/e)(1-m/k\epsilon^3)V_i\, \forall i$ with constant probability. For $m=o\big(k/\log^3 {k}\big)$ the factor is asymptotically $(1-1/e)$
\end{thm}



\begin{proof}{Proof
	From Lemma \ref{stage2} and applying Lemma \ref{swap} we have, $f_i(S_2|S_1)\geq (1-\epsilon) (1-1/e)(1-m/k\epsilon^3) (V_i-f_i(S_1)),\forall i$.
	Therefore, $f_i(S_1\cup S_2)\ge
	(1-\epsilon)(1-1/e)(1-m/k\epsilon^3)V_i,\forall i$. To refine the guarantee, we choose $\epsilon=\min\{\frac{1}{8\ln m},\sqrt[4]{\frac{m}{k}}\}$, where the $\frac{1}{8\ln m}$ is due to Lemma \ref{swap} and the $\sqrt[4]{\frac{m}{k}}$ term is to balance $\epsilon$ and $m/k\epsilon^3$. The resulting guarantee becomes $(1-1/e)(1-h(k))$, where the function $h(k)\to 0$ as $k\to \infty$, so long as $m=o\big(\frac{k}{\log^3 {k}}\big)$. 
	
	Note that the runtime is now independent of $\epsilon$. The first stage makes $O(mn)$ oracle queries, the second stage runs the continuous greedy algorithm on all functions simultaneously and makes $\tilde{O}(n^8)$ queries to each function oracle, contributing $O(mn^8)$ to the runtime. Stage 2 results in a fractional solution that can be written as a convex combination of $O(nk^2)$ sets of cardinality $k$ each (bases) (ref.\ Appendix A in \cite{vond1}). For cardinality constraint, swap rounding can merge two bases in $O(k)$ time hence, the last stage takes time $O(nk^3)$.
\end{proof}
\subsection{Fast, asymptotic $(1-1/e)^2-\delta$ approximation for $m=o\big(\frac{k}{\log^3 {k}}\big)$}\label{keyfast}
While the previous algorithm achieves the best possible asymptotic guarantee, it is infeasible to use in practice. The main underlying issue was our usage of the continuous greedy algorithm in Stage 2 which has runtime $\tilde{O}(mn^8)$, but the flexibility offered by continuous greedy was key to maximizing the multilinear extensions of all functions at once.
To improve the runtime we avoid continuous greedy and find an alternative
in Multiplicative-Weight-Updates (MWU) instead. MWU allows us to combine multiple submodular objectives together into a single submodular objective and utilize fast algorithms for $P_0$ at every step.

The algorithm consists of 3 stages as before. Stage 1 remains the same as the New Stage 1 introduced in the previous section. Let $S_1$ be the output of this stage as before.
Stage 2 is replaced with a fast MWU based subroutine that runs for $T=O(\frac{\ln m}{\delta^2})$ rounds and solves an instance of $SO$ during each round. Here $\delta$ is an artifact of MWU and manifests as a subtractive term in the approximation guarantee. The currently fastest algorithm for $SO$, in \cite{lazyfast}, has runtime $O(n\log \frac{1}{\delta'})$ and an \emph{expected} guarantee of $(1-1/e)-\delta'$. However, the slightly slower, but still nearly linear time $O(\frac{n}{\delta'}\log \frac{n}{\delta'})$ \emph{thresholding} algorithm in \cite{fast}, has (the usual) deterministic guarantee of $(1-1/e)-\delta'$. Both of these are known to perform well in practice and using either would lead to a runtime of $T\times \tilde{O}(n/\delta)=\tilde{O}(\frac{n}{\delta^3})$, which is a vast improvement over the previous algorithm. 

Now, fix some algorithm $\mathcal{A}$ for $P_0$ with guarantee $\alpha$, and let $\mathcal{A}(f,k)$ denote the set it outputs given monotone submodular function $f$ and cardinality constraint $k$ as input. Note that $\alpha$ can be as large as $1-1/e$, and we have $k_1=k-|S_1|$ as before. Then the new Stage 2 is, \\
\setcounter{algorithm}{1}
\begin{algorithm}[H]
	\caption{Stage 2: MWU}
	\label{mwu2}


	\begin{algorithmic}[1]
		\State {{\bf Input:} $\delta, T=\frac{2 \ln m}{\delta^2},\lambda^1_i=1/m,\tilde{f}_i(.)=\frac{f_i(.|S_1)}{V_i-f_i(S_1)}$}
		\While{$1\leq t\leq  T$} 
		$g^t(.)=\sum_{i=1}^{m} \lambda^t_i \tilde{f}_i(.)$\\
		$ X^t=\mathcal{A}(g^t,k_1)$ \\
		$m^t_i=\tilde{f}_i(X^t)-\alpha$\\
		$\lambda^{t+1}_i=\lambda^t_i (1-\delta m^t_i)$\\
		$t=t+1$
		\EndWhile
		\State {{\bf Output:} ${\bf x}_2=\frac{1}{T}\sum_{t=1}^T X^t$}
	\end{algorithmic}
\end{algorithm}




\emph{The point ${\bf x}_2$ obtained above is rounded to a set $S_2$ in Stage 3 (which remains unchanged). The final output is $S_1\cup S_2$}. Note that by abuse of notation we used the sets $X^t$ to also denote the respective support vectors. We continue to use $X^t$ and ${\bf x}_{X^t}$ interchangeably in the below.

This application of MWU is unlike \cite{azar,chekurimwu}, where broadly speaking the MWU framework is applied in a novel way to determine how an individual element is picked (or how a direction for movement is chosen in case of continuous greedy). In contrast, we use standard algorithms for $P_0$ and pick an entire set before changing weights. Also, \cite{chekurimwu} uses MWU along with the continuous greedy framework to tackle harder settings, but for our setting using the continuous greedy framework eliminates the need for MWU altogether and in fact, we use MWU as a replacement for continuous greedy. Subsequent to our work we discovered a resembling application of MWU in \cite{chen}. Their application differs from Algorithm \ref{mwu2} only in minor details, but unlike our result they give a bi-criterion approximation where the output is a set $S$ of cardinality up to $k\frac{\log m}{V\epsilon^2}$ such that $f_i(S)\geq(1-1/e-2\epsilon) V$.

Now, consider the following intuitive schema. We would like to find a set $X$ of size $k$ such that $f_i(X)\geq \alpha V_i$ for every $i$. While this seems hard, consider the combination $\sum_i \lambda_i f_i(.)$, which is also monotone submodular for non-negative $\lambda_i$. We can easily find a set $X_{\lambda}$ such that $\sum_i \lambda_i f_i(X_{\lambda})\geq \sum_i \lambda_i V_i$, since this is a single objective problem and we have fast approximations for $P_0$. However, for a fixed set of scalar weights $\lambda_i$, solving the $P_0$ problem instance need not give a set that has sufficient value for every individual function $f_i(.)$. This is where MWU comes into the picture. We start with uniform weights for functions, solve an instance of $P_0$ to get a set $X^1$. Then we change weights to undermine the functions for which $f_i(X^1)$ was closer to the target value and stress more on functions for which $f_i(X^1)$ was small, and repeat now with new weights. After running many rounds of this, we have a collection of sets $X^t$ for $t\in\{1,\dots,T\}$. Using tricks from standard MWU analysis (\cite{arora}) along with submodularity and monotonicity, we show that $\sum_t \frac{f_i(X^t|S_1)}{T}\gtrapprox (1-1/e)(V_i-f_i(S_1))$. Thus far, this resembles how MWU has been used in the literature for linear objectives, for instance the Plotkin-Shmoys-Tardos framework for solving LPs. However, a new issue now arises due to the non-linearity of functions $f_i$. As an example, suppose that by some coincidence ${\bf x}_2=\frac{1}{T}\sum_{t=1}^T X^t$ turns out to be a binary vector, so we easily obtain the set $S_2$ from ${\bf x}_2$. We want to lower bound $f_i(S_2|S_1)$, and while we have a good lower bound on $\sum_t \frac{f_i(X^t|S_1)}{T}$, it is unclear how the two quantities are related. More generally, we would like to show that $F_i({\bf x}_2|{\bf x}_{S_1})\geq \beta \sum_t \frac{f_i(X^t|S_1)}{T}$ and this would then give us a $\beta\alpha=\beta(1-1/e)$ approximation using Lemma \ref{swap}. Indeed, we show that $\beta\geq (1-1/e)$, resulting in a $(1-1/e)^2$ approximation. Now, we state and prove lemmas that formalize the above intuition.


\begin{lem}\label{feasible}
	$g^t(X^t)\geq \frac{k_1}{k}\alpha\sum_i\lambda^t_i	, \forall t$. 
\end{lem}
\begin{proof}{Proof}
	Consider the optimal set $S_k$ and note that $\sum_i \lambda^t_i \tilde{f}_i(S_k)\geq \sum_i \lambda^t_i, \forall t$. Now the function $g^t(.)=\sum_i \lambda^t_i \tilde{f}_i(.)$, being a convex combination of monotone submodular functions, is also monotone submodular. We would like to show that there exists a set $S'$ of size $k_1$ such that $g^t(S')\geq \frac{k_1}{k}\sum_i\lambda^t_i$. Then the claim follows from the fact that $\mathcal{A}$ is an $\alpha$ approximation for monotone submodular maximization with cardinality constraint. 
	
	To see the existence of such a set $S'$, greedily index the elements of $S_k$ using $g^t(.)$. Suppose that the resulting order is $\{s_1,\dots,s_k\}$, where $s_i$ is such that $g^t(s_i|\{s_1,\dots,s_{i-1}\})\geq g^t(s_j|\{s_1,\dots,s_{i-1}\})$ for every $j>i$. Then the truncated set $\{s_1,\dots,s_{k-|S_1|}\}$ has the desired property, and we are done.
\end{proof}
\begin{lem}\label{frommwu}

	$$	\frac{\sum_t \tilde{f}_i(X^t)}{T}\geq \frac{k_1}{k}(1-1/e)-\delta\, , \forall i.$$
\end{lem}  
\begin{proof}{Proof}
	Suppose we have,
	\begin{equation}
	\frac{\sum_t \tilde{f}_i(X^t)-\alpha}{T} +\delta \geq \frac{1}{T}\sum_t \sum_i \frac{\lambda^t_i}{\sum_i \lambda^t_i} (\tilde{f}_i(X^t)-\alpha),\forall i. \label{step}
	\end{equation}
	Then assuming $\alpha=(1-1/e)$, the RHS above simplifies to,
	\begin{eqnarray*}
		\frac{1}{T} \sum_t \frac{g(X^t)}{\sum_i \lambda^t_i}-(1-1/e) &&\geq (1-1/e)(\frac{k_1}{k}-1)\quad \text{(using Lemma \ref{feasible})}
	\end{eqnarray*}
	And we have for every $i$,
	\begin{eqnarray*}
		\frac{\sum_t \tilde{f}_i(X^t)-(1-1/e)}{T}+\delta &&\geq(1-1/e)(\frac{k_1}{k}-1)\\
		\frac{\sum_t \tilde{f}_i(X^t)}{T}&&\geq \frac{k_1}{k}(1-1/e)-\delta.
	\end{eqnarray*}
	Now, the proof for (\ref{step}) closely resembles the analysis in Theorem 3.3 and 2.1 in \cite{arora}. We will use the potential function $\Phi^t=\sum_i \lambda^t_i$. Let $p^t_i=\lambda^t_i/\Phi^t$ and $M^t=\sum_i p^t_i m^t_i$. Then we have,
	\begin{eqnarray*}
		\Phi^{t+1}&&=\sum_i \lambda^t_i (1-\delta m^t_i)\\
		&&=\Phi^t - \delta \Phi^t\sum_i p^t_i m^t_i\\
		&&=\Phi^t(1-\delta M^t) \leq \Phi^t e^{-\delta M^t}
	\end{eqnarray*}
	After $T$ rounds, $\Phi^T\leq \Phi^1 e^{-\delta\sum_t M^t}$. Further, for every $i$,
	\begin{eqnarray*}
		&\Phi^T\geq w^T_i =\frac{1}{m} \prod_t (1-\delta m^t_i)\\
		&\ln(\Phi^1 e^{-\delta\sum_t M^t})\geq \sum_t \ln (1-\delta m^t_i)-\ln m\\
		& \delta\sum_t M^t \leq \ln m + \sum_t \ln (1-\delta m^t_i)
	\end{eqnarray*}
	Using $\ln(\frac{1}{1-\epsilon})\leq \epsilon+\epsilon^2$ and $\ln (1+\epsilon)\geq \epsilon-\epsilon^2$ for $\epsilon\leq 0.5$, and with $T=\frac{2\ln m}{\delta^2}$ and $\delta< (1-1/e)$ (for a positive approximation guarantee), we have, $$\frac{\sum_t M^t}{T}\leq \delta + \frac{\sum_t m^t_i}{T},\forall i. $$
	
\end{proof}



\begin{lem}\label{key}
	Given monotone submodular function $f$, its multilinear extension $F$, sets $X^t$ for $t\in\{1,\dots,T\}$, and a point ${\bf x}=\sum_t X^t /T $, we have,	$$F({\bf x}) \geq (1-1/e)\frac{1}{T}\sum_{t=1}^T f(X^t).$$
\end{lem}  
\begin{proof}{Proof}
	Consider the concave closure of a submodular function $f$, 
	$$f^+({\bf x})=\max_{{\bf \alpha}}\{\sum_{X} \alpha_Xf(X)|\sum_{X} \alpha_X X={\bf x}, \sum_{X} \alpha_X\leq 1, \alpha_X\geq 0\, \forall X\subseteq N\}.$$ Clearly, $f_i^+({\bf x})\geq \frac{\sum_t f_i(X^t)}{T}$.  So it suffices to show $F_i({\bf x}) \geq (1-1/e)f^+_i({\bf x})$, which in fact, follows from Lemmas 4 and 5 in \cite{calines}.

	
	Alternatively, we now give a novel and direct proof for the statement. We abuse notation and use ${\bf x}_{X^t}$ and $X^t$ interchangeably.
	Let ${\bf x}=\sum_{t=1}^{T}  X^t/T$ and w.l.o.g., assume that sets $X^t$ are indexed such that $f(X^j)\geq f(X^{j+1})$ for every $j\geq 1$. Further, let $f(X^t)/T=a^t$ and $\sum_t a^t=A$.

	
	Recall that $F({\bf x})$ can be viewed as the expected function value of the set obtained by independently sampling element $j$ with probability $x_j$. Instead, consider the alternative random process where starting with $t=1$, one samples each element in set $X^t$ independently with probability $1/T$. The random process runs in $T$ steps and the probability of an element $j$ being chosen at the end of the process is exactly $p_j=1-(1-1/T)^{Tx_j}$, independent of all other elements. Let ${\bf p}=(p_1,\dots,p_n)$, it follows that the expected value of the set sampled using this process is given by $F({\bf p})$. Observe that for every $j$, $p_j\leq x_j$ and therefore, $F({\bf p})\leq F({\bf x})$. Now in step $t$, suppose the newly sampled subset of $X^t$ adds marginal value $\Delta^t$. From submodularity we have, $\mathbb{E}[\Delta^1]\geq\frac{f(X^1)}{T}= a^1$ and in general, $\mathbb{E}[\Delta^t]\geq\frac{f(X^t)-\mathbb{E}[\sum_{j=1}^{t-1} \Delta_j]}{T}\geq a^t-\frac{1}{T}\sum_{j=1}^{t-1}\mathbb{E}[\Delta^j]$
	
	To see that $\sum_t \mathbb{E}[\Delta^t]\geq (1-1/e)A$, consider a LP where the objective is to minimize $ \sum_t \gamma^t$ subject to $b^1\geq b^2\dots\geq b^T\geq 0$; $\sum b^t=A$ and $\gamma^t\geq b^t-\frac{1}{T}\sum_{j=1}^{t-1}\gamma^j$ with $\gamma^0=0$. Here $A$ is a parameter and everything else is a variable. Observe that the extreme points are characterized by $j$ such that, $\sum b^t= A$ and $b^t=b^1$ for all $t\leq j$ and $b^{j+1}=0$. For all such points, it is not difficult to see that the objective is at least $(1-1/e)A$. Therefore, we have $F({\bf p})\geq (1-1/e)A=(1-1/e)\sum_t f(X^t)/T$, as desired. 
	
\end{proof}

\begin{thm}
	For $\epsilon=\min\{\frac{1}{8\ln m},\sqrt[4]{\frac{m}{k}}\}$, the algorithm makes $O(\frac{n}{\delta^3}\log m\log \frac{n}{\delta})$ queries, and with constant probability outputs a feasible $(1-\epsilon)(1-1/e)^2(1-\frac{m}{k\epsilon^3})-\delta$ approximate set. Asymptotically, $(1-1/e)^2-
	\delta$ approximate for $m=o\big(k/\log^3 {k}\big)$.
\end{thm}
\begin{proof}{Proof}













	Combining Lemmas \ref{frommwu} \& \ref{key} we have, $\tilde{F}_i({\bf x}_2)\geq(1-1/e) \frac{\sum_t \tilde{f}_i(X^t)}{T}\geq \frac{k_1}{k}(1-1/e)^2-\delta\, , \forall i$. The asymptotic result follows just as in Theorem \ref{extension}.








	For runtime, note that Stage 1 takes time $O(n)$. Stage 2 runs an instance of $\mathcal{A}(.)$, $T$ times, leading to an upper bound of $O((\frac{n}{\delta}\log \frac{n}{\delta})\times \frac{\log m}{\delta^2})=O(\frac{n}{\delta^3}\log m\log \frac{n}{\delta})$, if we use the thresholding algorithm in \cite{fast} (at the cost of a multiplicative factor of $(1-\delta)$ in the approximation guarantee).
	Finally,
	swap rounding proceeds in $T$ rounds and
	each round takes $O(k)$ time, leading to total runtime $O(\frac{k}{\delta^2}\log m)$ for Stage 3. Combining all three we get a runtime of $O(\frac{n}{\delta^3}\log m\log \frac{n}{\delta})$.
\end{proof}

\subsection{Variation in optimal solution value and derandomization}\label{resolve}
Consider the problem $P_0$ with cardinality constraint $k$. Given an optimal solution $S_k$ with value $OPT_k$ for the problem, it is not difficult to see that for arbitrary $k'\leq k$, there is a subset $S_{k'}\subseteq S_k$ of size $k'$, such that $f(S_{k'})\geq \frac{k'}{k} OPT_k$. For instance,
indexing the elements in $S_k$ using the greedy algorithm, and choosing the set given by the first $k'$ elements gives such a set. This implies $OPT_{k'}\geq \frac{k'}{k} OPT_k$, and the bound is easily seen to be tight.

This raises a natural question: Can we generalize this bound on variation of optimal solution value with varying $k$, for multi-objective maximization? A priori, this isn't obvious even for modular functions. In particular, note that indexing elements in order they are picked by the greedy algorithm doesn't suffice since there are many functions and we need to balance values amongst all. We show below that one can indeed derive such a bound.

\begin{lem}\label{variation}
	Given that there exists a set $S_k$ such that $f_i(S_k)\geq V_i,\forall i$ and $\epsilon< \frac{1}{8\ln m}$. For every $k'\in[m/\epsilon^3 , k]$, there exists $S_{k'}\subseteq S_k$ of size $k'$, such that, $$f_i(S_{k'})\geq(1-\epsilon)\Big(\frac{k'-m/\epsilon^3}{k-m/\epsilon^3} \Big)V_i,\forall i .$$
\end{lem}
\begin{proof}{Proof}


	We restrict our ground set of elements to $S_k$ and let $S_1$ be a subset of size at most $m/\epsilon^3$ such that $f_i(e|S_1)<\epsilon^3 V_i, \forall e\in S_k\backslash S_1 \text{ and }\forall i$ (recall, we discussed the existence of such a set in Section 2.1, Stage 1). The rest of the proof is similar to the proof of Lemma \ref{stage2}.

	Consider the point ${\bf x}=\frac{k'-|S_1|}{k-|S_1|}{\bf x}_{S_k\backslash S_1}$. Clearly, $|{\bf x}|=k'-|S_1|$, and from Corollary \ref{concavity}, we have $F_i({\bf x}|{\bf x}_{S_1})\geq\frac{k'-|S_1|}{k-|S_1|}F_i({\bf x}_{S_k\backslash S_1}|{\bf x}_{S_1})=\frac{k'-|S_1|}{k-|S_1|}f_i(S_k\backslash S_1|S_1)\geq  \frac{k'-|S_1|}{k-|S_1|}(V_i-f_i(S_1)),\forall i$. Finally, using swap rounding Lemma 1, there exists a set $S_2$ of size $k'-|S_1|$, such that $f_i(S_1\cup S_2)\geq (1-\epsilon)\frac{k'-|S_1|}{k-|S_1|}V_i,\forall i$. 
	

\end{proof}
{\bf Conjecture in \cite{ipcofull}}: Note that this resolves a slightly weaker version of the conjecture in \cite{ipcofull} for constant $m$.
The original conjecture states that for constant $m$ and every $k'\geq m$, there exists a set $S$ of size $k'$, such that $f_i(S)\geq \frac{k'-\Theta(1)}{k} V_i,\forall i$. Asymptotically, both $\frac{k'-m/\epsilon^3}{k-m/\epsilon^3}$ and $\frac{k'-\Theta(1)}{k}$ tend to $\frac{k'}{k}$. This implies that for large enough $k'$, we can choose sets of size $k'$ ($k'$-tuples) at each step to get a deterministic (asymptotically) $(1-1/e)-\epsilon$ approximation with runtime $O(kn^{m/\epsilon^4})$ for the multi-objective maximization problem, when $m$ is constant (all previously known approximation algorithms, as well as the ones presented earlier, are randomized).
\begin{thm}
	For $k'=\frac{m}{\epsilon^4}$, choosing $k'$-tuples greedily w.r.t.\ $h(.)=\min_i f_i(.)$ yields approximation guarantee $(1-1/e)(1-2\epsilon)$ for $k\to \infty$, while making $n^{m/\epsilon^4}$ queries.
\end{thm}
\begin{proof}{Proof}
	The analysis generalizes that of the standard greedy algorithm (\cite{nem1,nem}). Let $S_j$ denote the set at the end of iteration $j$. $S_0=\emptyset$ and let the final set be $S_{\floor*{k/k'}}$. Then from Theorem \ref{variation}, we have that at step $j+1$, there is some set $X\in S_k\backslash S_{j}$ of size $k'$ such that 
	$$f_i(X|S_{j})\geq (1-\epsilon)\frac{k'-m/\epsilon^3}{k-m/\epsilon^3}\big(V_i-f_i(S_j)\big), \forall i.$$ 
	To simplify presentation let $\eta=(1-\epsilon)\frac{k'-m/\epsilon^3}{k-m/\epsilon^3}$ and note that $\eta\leq 1$. Further, $1/\eta\to \infty$ as $k\to \infty$ for fixed $m$ and $k'=o(k)$. Now, we have for every $i$, $f_i(S_{j+1})-(1- \eta)f_i(S_j)\geq \eta V_i$. Call this inequality $j+1$. Observe that inequality $\floor*{k/k'}$ states $f_i(S_{\floor*{k/k'}})-(1-\eta)f_i(S_{\floor*{k/k'}-1})\geq \eta V_i,\forall i$. Therefore, multiplying inequality $\floor*{k/k'}-j$ by $(1-\eta)^j$ and telescoping over $j$ we get for every $i$,
	\begin{eqnarray*}
		f_i(S_{\floor*{k/k'}})&&\geq \sum_{j=0}^{\floor*{k/k'}-1} (1-\eta)^j \eta V_i\\
		&&\geq \big(1-(1-\eta)^{\floor*{k/k'}})V_i\\
		&&\geq  \big(1-(1-\eta)^{\frac{1}{\eta} \eta\floor*{k/k'}})V_i\\
		&&\geq \beta(\eta \floor*{k/k'})V_i\quad  \geq (1-1/e)(\eta \floor*{k/k'})V_i.
	
	
	
	\end{eqnarray*}
	Where we used (\ref{simfact}) for the last inequality. Let $\epsilon=\sqrt[4]{\frac{m}{k'}}$, then we have,
	\begin{eqnarray*}
		\eta \floor*{k/k'}\geq (1-\epsilon)\frac{1-m/k'\epsilon^3}{1-m/k\epsilon^3} \Big(1-\frac{k'}{k}\Big)\geq\frac{\Big(1-\sqrt[4]{\frac{m}{k'}}\Big)^2}{1-\frac{1}{k}\sqrt[4]{\frac{m}{(k')^3}}}\Big(1-\frac{k'}{k}\Big)
	\end{eqnarray*} 
	As $k\to \infty$ we get the asymptotic guarantee $(1-1/e)\Big(1-\sqrt[4]{\frac{m}{k'}}\Big)^2=(1-1/e)(1-\epsilon)^2$.
\end{proof}




\section{Experiments on Kronecker Graphs}

We choose synthetic experiments where we can control the parameters to see how the algorithm performs in various scenarios, esp.\ since we would like to test how the MWU algorithm performs for small values of $k$ and $m=\Omega(k)$.
We work with formulation $P_1$ of the problem and consider a multi-objective version of the \textit{max-k-cover} problem on graphs.
Random graphs for our experiments were generated using the Kronecker graph framework introduced in \cite{kron}. These graphs exhibit several natural properties and are considered a good approximation for real networks (esp. social networks \cite{influ}).  

We compare three algorithms: (i) A baseline greedy heuristic, labeled GREEDY, which focuses on one objective at a time and successively picks $k/m$ elements greedily w.r.t.\ each function (formally stated below). (ii) A bi-criterion approximation called SATURATE from \cite{main}, to the best of our knowledge this is considered state-of-the-art for the problem. (iii) We compare these algorithms to a heuristic inspired by our MWU algorithm. This heuristic differs from the algorithm discussed earlier in two ways. Firstly, we eliminate Stage 1 which was key for technical analysis but in practice makes the algorithm perform similar to GREEDY. Second, instead of simply using the the swap rounded set $S_2$, we output the best set out of $\{X^1,\dots,X^T\}$ and $S_2$. Also, for both SATURATE and MWU we estimate target value $t$ using binary search and consider capped functions $\min \{f_i(.),t\}$. Also, for the MWU stage, we used $\delta=0.5$ or $0.2$

\setcounter{algorithm}{2}
\begin{algorithm}[H]
	\caption{GREEDY}
	


	\begin{algorithmic}[1]
		\State {{\bf Input:} $k,m,f_i(.)\text{ for } i\in[m]$}
		\State $S=\emptyset, i=1$
		\While{$|S|\leq k-1$}\\ 
		$S=S+ \arg\max_{x\in N-S} f_i(x|S)$\\
		$i= i+1 \mod m+1$
		\EndWhile
		\State {{\bf Output:} $S$}
	\end{algorithmic}
\end{algorithm} 
\begin{algorithm}[H]
	\caption{SATURATE}\label{saturate}
	\begin{algorithmic}[1]
		\State Input: $k,t,f_1,\dots,f_m$ and set $A=\emptyset$
		\State $g(.)= \sum_i \min\{f_i(.),t\}$
		\While{$|A|< k$} $A=A+\argmax{x\in N-A} g(x|A)$ \EndWhile
		\vspace{-3mm}
		\State Output: $A$
	\end{algorithmic}
\end{algorithm}
We pick Kronecker graphs of sizes $n\in \{64,512,1024\}$ with random initiator matrix \footnote{To generate a Kronecker graph one needs a small initiator matrix. Using \cite{kron} as a guideline we use random matrices of size $2\times2$, each entry chosen uniformly randomly (and independently) from $[0,1]$. Matrices with sum of entries smaller than 1 are discarded to avoid highly disconnected graphs.} and for each $n$, we test for $m\in \{10,50,100\}$. Note that each graph here represents an objective, so for a fixed $n$, we generate $m$ Kronecker graphs to get $m$ \textit{max-cover} objectives. For each setting of $n,m$ we evaluate the solution value for the heuristics as $k$ increases and show the average performance over 30 trials for each setting.
All experiments were performed using MATLAB.	
\begin{figure}[H]
	\centering
	\includegraphics[scale=0.4]{64.png
	\caption{Plots for graphs of size 64. Number of objectives increases from left to right. The X axis is the cardinality parameter $k$ and Y axis is difference between \# vertices covered by MWU and SATURATE minus the \# vertices covered by GREEDY for the same $k$. MWU outperforms the other algorithms in all cases, with a max.\ gain (on SATURATE) of 9.80\% for $m=10$, 12.14\% for $m=50$ and  16.12\% for $m=100$.}



\end{figure}
\begin{figure}[H]

	\centering
	\includegraphics[scale=0.4]{512.png
	\caption{Plots for graphs of size 512. MWU outperforms SATURATE in all cases with a max.\ gain (on SATURATE) of 7.95\% for $m=10$, 10.08\% for $m=50$ and  10.01\% for $m=100$.}
	



\end{figure}
\begin{figure}[H]

	\centering
	\includegraphics[scale=0.4]{1024n.png
	\caption{Plots for graphs of size 1024. MWU outperforms SATURATE in all cases, with max. gain (on SATURATE) of 6.89\% for $m=10$, 5.02\% for $m=50$ and  7.4\% for $m=100$.}



\end{figure}
\section{Conclusion and Open Problems}
In summary, we consider the problem of multi-objective maximization of monotone submodular functions subject to a cardinality constraint, when $m=o\big(\frac{k}{\log^3 {k}}\big)$. No polynomial time constant factor approximations or strong inapproximability results were known for the problem, though it was known that the problem is inapproximable when $m=\Omega(k)$ and admitted a nearly $1-1/e$ approximation for constant $m$. We showed that when $m=o\big(\frac{k}{\log^3 {k}}\big)$, one can indeed approach the best possible guarantee of $1-1/e$ and further also gave a nearly-linear time $(1-1/e)^2$ approximation for the same. Finally, we established a natural bound on how the optimal solution value increases with increasing cardinality $k$ of the set, leading to a simple deterministic algorithm

A natural open question here is whether one can achieve approximations right up to $m=o(k)$. Additionally, it also of interest to ask if there are fast algorithms with guarantee closer to $1-1/e$, in contrast to the guarantee of $(1-1/e)^2$ shown here. Further, it is unclear if similar results can also be shown for a general matroid constraint.
\section*{Acknowledgments}
	The author gratefully acknowledges partial support from ONR Grant N00014-17-1-2194. The author would also like to thank James B. Orlin and anonymous referees for their insightful comments and feedback on early drafts of this work.

	






















 \bibliographystyle{plain}
