\section{Appendix}
\label{sec:appendix}
\newcommand{\cM} { {\cal M}}

\subsection{Applications of {\sf Group GAP}}
\label{sec:appendix_applics}
As a primary motivation for our study, consider wireless networks~(see, e.g., \cite{KPCK14,WZSL17}) a carrier supplies a set of data items to a set of users upon demand.
Each user has an isolated cache memory of a given size; each item
consists of a set of blocks. Time is slotted. The carrier smooths out the network load by caching at time $t=0$ data block within the user caches, and later lets the users
share these blocks at time $t \geq 1$ via a D2D (Device-to-Device) network. There is a utility associated with storing a data block of an item in each user cache (depending, e.g., on the location of this user in the network).
Thus, viewing each item as a group of blocks, finding a feasible allocation of data blocks in the users caches so as to maximize the total utility yields an instance of {\sf Group GAP}.

{\sf Group GAP} has a central application also in 5G networks.
Caching at small-cell base stations (SBSs) to meet the overwhelming growth in mobile data demand is expected to
be utilized in the next generation (5G) cellular networks~\cite{PT16,BBD14}.
This technique leverages the expected deployment of short-range, low-power, and low-cost SBSs in cellular networks.
It is expected that this will enable immersive Virtual Reality (VR) and Augmented Reality (AR) mobile applications that are currently limited to off-line settings~\cite{Chak17}.
A VR/AR $360^{\circ}$-navigable 3D video presents
the user with an interactive immersive visual representation of the
remote scene of interest that the user can navigate from any possible
3D viewpoint. To enable such capability in a mobile device with limited computation power and storage, the 3D video is decomposed into different
views and {\em all} these views must be cached in the SBSs.
There is a utility associated with storing a specific view in each SBS (depending, e.g., on the projected popularity of this view, its size relative to the cache size, etc.).
Thus, viewing each 3D video as a group of views, finding a feasible allocation of these views to SBSs to maximize the total utility yields an instance of
{\sf Group GAP}.

\subsection{Some Proofs}
\label{sec:appendix_proofs}
\noindent
{\bf Proof of Theorem \ref{thm:shmoys_trados}:}
Let $S=I(G^*)$.
We first note that since $s(S)=s(I(G^*)) \leq m$, any fractional solution $x$ can be modified to a solution $x'$ of at least the same profit, such that for all
$i\in S$ it holds that $\sum_{j\in M} x'_{i,j} = 1$.
Thus, we may assume that
for any $i\in S$ we have $\sum_{j\in M} x_{i,j} =1$.
W.l.o.g., assume  the items are ordered by their size; that is,
$s_1 \geq s_2 \geq \ldots \geq s_n$.
We use Algorithm~\ref{alg:st_construct} to generate
a bipartite graph $G = (S, R, E)$ with weight $w_e \geq 0$ on any edge $e \in E$,
and a fractional matching $x'$ in $G$.

We note the following observations about Algorithm~\ref{alg:st_construct}.

\begin{itemize}
	\item
	The algorithm returns a fractional matching $x'$ which is complete for $S$.
	For each item $i\in S$ and bin $j\in M$ it holds that
	$x_{i,j} = \sum_{e=(i,(j,r) )\in E} x'_e$. Therefore,
	the weight of $x'$ is equal to the profit of the solution $x$ for
	the  $\mbox{LP}$, i.e., $w(x') = p\cdot x$.

	\item  For any bin $j\in M$ let $k_j$ be the maximum number such
	that $(j,k_j) \in R$. For any $1\leq r \leq k_j$ let
	$s_{j,r} ^{\max} = \max\{ s_i | (i,(j,r))\in E\}$ and
   $s_{j,r} ^{\min} = \min\{ s_i | (i,(j,r))\in E\}$.
   By the construction, it is easy to see that
   $s_{j,1}^{\max}\geq s_{j,1}^{\min}\geq s_{j,2}^{\max} \geq s_{j,2}^{\min}\geq \ldots
   s_{j,k_j}^{\max}\geq s_{j,k_k}^{min}$
	\item For any bin $j\in M$ and $1\leq r <k_j$ we have $\sum_{i|(i,(j,r))\in E} x'_{(i,(j,r))} = 1$.
\end{itemize}

Using standard results from matching theory
 (see, e.g.,~\cite{LP09}), there is a matching $\cM$ for $G$
which is complete for $S$  and $\sum_{e\in M} w_e \geq w(x')$. Such
a matching $\cM$ can also be found in polynomial time.

We define an assignment based on $\cM$; that is,
for every bin $j\in M$ and $1\leq r \leq k_j$ set
$U_{j,r}= \{i\in S| (i,(j,r))\in \cM\}$. Now, define
for every $j\in M$: $U_j =\bigcup_{r=1}^{k_j} U_{j,r}$ and $U = (U_1, U_2,\ldots, U_m)$.
As $\cM$ is complete for $S$, each element $i\in S$ is assigned to a single bin,
and each of the sets $U_{j,r}$ contains at most a single element.
Now, for every $j \in M$ we have
\begin{equation}
\label{eq:almost_feasible}
\begin{aligned}
\displaystyle{ \sum_{i \in U_j} s_i }  & =  \displaystyle{\sum_{r=1}^{k_j} \sum_{i \in U_{j,r}} s_i
 \leq
 \sum_{i\in U_{j,1}} s_i + \sum_{r=2}^{k_j} s_{j,r}^{\max}
   \leq
   \sum_{i\in U_{j,1}} s_i  + \sum_{r=1}^{k_j-1} s_{j,r}^{\min}}
  \\  \\
  &=  \displaystyle{  \sum_{i\in U_{j,1}} s_i  + \sum_{r=1}^{k_j-1}\sum_{\{i| (i, (j,r))\in E\}} x'_{(i,(j,r))}  s_{j,r}^{\min} }
  \\ \\
  & \leq
 \displaystyle{\sum_{i\in U_{j,1}} s_i  + \sum_{r=1}^{k_j-1}\sum_{\{i| (i, (j,r))\in E\}} x'_{(i,(j,r))} s_i
  \leq
   \sum_{i\in U_{j,1}} s_i  + \sum_{i\in S} x_{i,j} s_i}
  \\ \\
  & \leq
  \displaystyle{1+ \sum_{i\in U_{j,1}} s_i}
\end{aligned}
\end{equation}
The
first inequality follows from the definition of $s_{j,r}^{\max}$ and $|U_{j,r}| \leq 1$.
The second inequality holds since $s_{j,r}^{\max} \leq s_{j,r-1}^{\min}$.
The second equality holds since $\sum_{i|(i,(j,r))\in E} x'_{(i,(j,r))} = 1$ for $1\leq r<k_j$.
In the third inequality we use the definition of $s_{j,r}^{\min}$, and
the fourth  inequality follows from $x_{i,j} = \sum_{e=(i,(j,r) )\in E} x'_e$.
The last inequality holds since $x$ is a (feasible) solution for $\mbox{LP}(S)$.

\begin{algorithm}
	\caption{Bipartite Construction}
	\label{alg:st_construct}

	\begin{algorithmic}[1]
		\State Set $R=E=\emptyset$
		\For {$j\in M$}
		\State Set $r=1$ and $c_r=0$, add $(j,1)$ to $R$
		\For {$i$ from $1$ to $n$ such that $x_{i,j}>0$}
		\State Add an edge $e=(i,(j,r))$ to $E$, $w_e =p_{i,j}$
					and set $x'_e = \min(x_{i,j}, 1-c_r)$
		\State Update $c_r = c_r + x'_e$.
		\If{$x_{i,j} \neq x'_e$}
			\State Add $(j,r+1)$ to $R$ and $f= (i,(j,r+1))$ to $E$.
			 \State Set  $w_f = p_{i,j}$, $x'_f  = x_{i,j} -  x'_e$, $r=r+1$ and  $c_r = x'_f$.
		\EndIf
		\EndFor

		\EndFor
		\State Return $G=(S, R, E)$, the weights $w$ and the
		fractional matching $x'$.
	\end{algorithmic}

\end{algorithm}

By inequality \eqref{eq:almost_feasible} and since $U_{j,1}$ contains at most a single element, we have that $U$ is an almost
feasible assignment.  We note that the profit of the assignment $U$ is
exactly the weight of the matching $\cM$, which is at least the profit
of $x$.

This suggests the following conversion procedure. Given a solution $x$ for $\mbox{LP}(S)$, use Algorithm \ref{alg:st_construct} to obtain a bipartite graph $G= (S, R, E)$ with weights $w$. Find a
maximal weight matching $\cM$ in $G$ which is complete for $S$. Define an assignment
 $U$ using $\cM$ and return this assignment.
 By the above discussion, this procedure is polynomial and returns an assignment
 as required by the theorem.
\qed

\noindent
{\bf Proof of Theorem~\ref{thm:submod_bp_matching}:}
Consider two subsets $S\subset T \subset A$. Let $v\in A\setminus T$. To prove submodularity we show that $h(S\cup\{v\})-h(S) \ge h(T\cup\{v\})-h(T)$.

Let $S' = S\cup\{v\}$ and $T' = T\cup\{v\}$. For a subset $X\subseteq A$ let $M_X$ be a matching whose weight achieves $h(X)$. (Note that there may be more than one such matching, we fix one arbitrarily.) For $u \in X$, define $M_X(u)$ to be the vertex in $B$ that is matched to $u$.
Also, for $Y\subseteq X$ let $M_X(Y)$ be the set of matching {\em edges} that touch the vertices in $Y$. That is, $M_X(Y) =\cup_{y\in Y} \{(y,M_X(y))\}$.

To prove the theorem we need the following lemma.
\begin{lemma}
\label{lem:augPath}
There exists a subset $X=\{x_1=v,\ldots,x_k\}\subseteq S'$, for some $k\ge 1$,
with the following two properties.
\begin{enumerate}
\item
For $i\in [1..k-1]$, $M_{S}(x_{i+1}) = M_{T'}(x_{i})$
\item
$M_{T'}(x_k)$ is not matched in $M_S$
\end{enumerate}
\end{lemma}
Before we prove the lemma, we show how it implies the theorem.
Let $E_1 = M_S(X\setminus\{x_1\})$, and $E_2 = M_{T'}(X)$.

We claim that $h(S')-h(S) \ge W(E_2)-W(E_1)$. Consider the set of edges $E_2
\cup M_S(S\setminus X)$. Notice that it is a matching in the subgraph induced by
$S'\cup B$. Clearly, $h(S') \ge W(E_2 \cup M_S(S\setminus X)) =
W(E_2)+W(M_S(S\setminus X))$. Also, by definition,
$h(S)=W(E_1\cup M_S(S\setminus X)) = W(E_1)+W(M_S(S\setminus X))$.
Thus, $h(S')-h(S) \ge W(E_2)-W(E_1)$.

We claim that $h(T')-h(T) \le W(E_2)-W(E_1)$. By definition,
$h(T')=W(E_2\cup M_{T'}(T\setminus X)) = W(E_2)+W(M_{T'}(T\setminus X))$.
Consider the set of
edges $E_1 \cup M_{T'}(T\setminus X)$. Notice that it is a matching in the
subgraph induced by $T\cup B$. Clearly,
$h(T) \ge W(E_1 \cup M_{T'}(T\setminus X)) = W(E_1)+W(M_{T'}(T\setminus X))$.
Thus, $h(T')-h(T) \le W(E_2)-W(E_1)$. The proof follows.
\hfill \qed

\begin{dl_proof}{\ref{lem:augPath}}
We build $X$ iteratively. We start with $X=\{v\}$. If $M_{T'}(v)$ is not
matched in $M_S$, we are done since $X$ satisfies both properties. (The first
property is satisfied vacuously.) Otherwise, define $x_2$ to be the vertex that
satisfies  $M_S(x_2) = M_{T'}(x_1=v)$. Note that $x_2\ne x_1$. Also,
$X=\{x_1,x_2\}$ satisfies the first property by definition. If $M_{T'}(x_2)$ is
not matched in $M_S$, we are done since $X$ satisfies both properties.
Otherwise, define $x_3$ to be the vertex that satisfies   $M_S(x_3) =
M_{T'}(x_2)$. Note that $x_3 \notin \{x_1,x_2\}$. We continue in the same manner
if we are not done. Namely, at stage $i$ we have the set $\{x_1,\ldots,x_i\}$
that satisfies the first property. If $M_{T'}(x_i)$ is not matched in $M_S$, we
are done. Otherwise, define $x_{i+1}$ to be the vertex that satisfies
$M_S(x_{i+1}) = M_{T'}(x_i)$.  Again, $x_{i+1} \notin \{x_1,\ldots,x_i\}$. Since
in each stage we add a new vertex from $S$,  and $S$ is finite, we are guaranteed
to be done at some stage.
\end{dl_proof}

\remove{
\bigskip
\noindent
{\bf Proof of Lemma \ref{thm:sub_technical}:}
Let $p_1, p_2, S_1, S_2$ be values that satisfy the conditions in the lemma.
Denote $p = p_1 + p_2$, $d= p_1 - p_2$ and $r = \exp\left(-\frac{\frac{1}{2} - S_1} {1 -S_1 -S_2}\right)$.
It is easy to see that $\exp\left(-\frac{\frac{1}{2} - S_2} {1 -S_1 -S_2}\right) = \frac{e^{-1}}{r}$.
Define $V_1 = h(p_1, p_2, S_1, S_2)$ and $V_2 = h(p_2, p_1, S_2, S_1)$.  By the definition of $h$ and above
definitions we get
$$V_1 = \frac{p+d}{2} +(1-p)(1-r) - \frac{p}{k}$$
and
$$V_2 = \frac{p-d}{2} +(1-p)\left(1-\frac{e^{-1}}{r}\right) - \frac{p}{k}$$
Let $g_1(x) = \frac{p+d}{2} +(1-p)(1-x) - \frac{p}{k}$
and $g_2(x) = \frac{p-d}{2} +(1-p)\left(1-\frac{e^{-1}}{x}\right) - \frac{p}{k}$.
Clearly, $V_1 = g_1(r)$ and $V_2 = g_2(r)$. It is also easy to
see that $g_1$ is decreasing and $g_2$ is increasing (for $x>0$).
\begin{claim}
	It holds that $g_1(x^*) = g_2(x^*)$ where  $x^*= \frac{d + \sqrt{d^2 + 4e^{-1} (1-p)^2}}{2(1-p)}$.

\end{claim}
\begin{proof}
	By rearranging terms we have  $g_1(x) = g_2(x)$
	if and only if $d = (1-p) ( x -\frac{e^{-1}}{x})$, which holds
	for $x>0$ if and only if
	$0 = (1-p) x^2 -dx -e^{-1}(1-p)$. The latter is a quadratic
	equation and $x^*>0$ is a root.
\end{proof}

If $r\geq x^*$, since $g_2$ is increasing, we have $V_2 = g_2(r) \geq g_2(x^*) = g_1(x^*)$, and if $r\leq x^*$, as $g_1$ is decreasing, we have $V_1 = g_1(r) \geq g_1(x^*)$. Therefore $\max (V_1, V_2) \geq g_1(x^*)$.

Consider two cases:

\noindent
{\bf Case 1:} $p\leq \frac{1}{3}$. We have $|d|\leq p$  and
$$g_1(x^*) = 1-\frac{p}{2} -\frac{\sqrt{d^2 + 4e^{-1}(1-p)^2}}{2} - \frac{p}{k} \geq 1-  \frac{p}{2} - \frac{p}{k} - \frac{\sqrt{p^2 + 4e^{-1}(1-p)^2}}{2}.$$

Let $a(y) = 1- \frac{y}{2} - \frac{y}{k} - \frac{\sqrt{y^2 + 4e^{-1}(1-y)^2}}{2}$. Clearly, $g_1(x^*)\geq a(p)$.
We note that $a''(y)= -\frac{2e^{-1}} {( y^2+ 4e^{-1} (1-y)^2 )^{\frac{3}{2}}} $.
As $a''(y) < 0$, $a(y)$ does not have
a local minima in $[0, \frac{1}{3}]$. Thus as $p\in [0, \frac{1}{3}]$
we have $$g_1(x^*)\geq a(p) \geq \min\left( a(0), a\left(\frac{1}{3}\right)\right) = \min \left( 1-e^{-0.5}, \frac{5}{6}- \frac{1}{3k} -\frac{\sqrt{1+16e^{-1}}}{6}\right) \geq \frac{1}{3}$$

\noindent
{\bf Case 2:} $p\geq  \frac{1}{3}$, as $\frac{p+d}{2}, \frac{p-d}{2} \leq \frac{1}{3}$ we have that $|d| \leq \frac{2}{3}- p$. Therefore,
$$g_1(x^*) = 1-\frac{p}{2} -\frac{\sqrt{d^2 + 4e^{-1}(1-p)^2}}{2} - \frac{p}{k} \geq 1-  \frac{p}{2} - \frac{p}{k} - \frac{\sqrt{(\frac{2}{3}-p)^2 + 4e^{-1}(1-p)^2}}{2}$$
Let  $b(z) = 1- \frac{z}{2} - \frac{z}{k} - \frac{\sqrt{(\frac{2}{3} - z)^2 + 4e^{-1}(1-z)^2}}{2}$. Clearly, $g_1(x^*) \geq b(p)$.  We note
that $$b''(z) = -\frac{2e^{-1}}{9 \left( 4e^{-1}(1-z)^2 +(\frac{3}{2}-z )^2 \right) ^{\frac{3}{2}}}<0.$$
Thus,  $b(z)$ does not have a local minima in $[\frac{1}{3}, \frac{2}{3}]$. Hence, we have that $g_1(x^*) \geq b(p) \geq \min(b(\frac{1}{3}),b( \frac{2}{3})) \geq \frac{1}{3}$.

In both cases we get $g_1(x^*)\geq\frac{1}{3}$, and as $\max(V_1, V_2)\geq g_1(x^*)$, the lemma immediately follows.
\hfill \qed
}

\subsection{Missing Details in the Proof of Theorem \ref{thm:halfsvi}}
\label{app:sec4_details}
\begin{lemma}
	\label{thm:alpha_greedy}
	Let $S^* \subseteq {\Omega}$ be a non-empty subset of items, such that $s(S^*) \leq m^*$. Also, let

	$g: 2^{\Omega} \rightarrow \rm I\!R$
	be a submodular, non-negative and monotone function such that $g(\emptyset)=0$,  and $S=\Call{Greedy}{g,m'}$.
	Then, for any subset $T \subseteq {\Omega}$,
	there is an item $i^*\in S^*$ such that
	$g(S)+g_T(\{i^*\})\geq (1-e^{m'/m^*}) g_T(S^*)$.
\end{lemma}

\begin{proof}
	If $S^* \subseteq S$ then the claim trivially holds. Thus, we may assume
	that $S^* \nsubseteq S$.
	Let $S = \{i_1, i_2, \ldots, i_\ell\}$, where the elements are in the order they
	were added to $S$ during the execution of {\sc Greedy}.

	Let $S_r =\{ i_1, i_2, \ldots, i_r \}$ denote the first $r$ items in $S$, $0 \leq r \leq \ell$, where $S_0=\emptyset$. We denote by

	$\theta_r = \frac{g_{S_{r-1}} (\{i_r\})}{s_{i_r}}$ the marginal gain density from adding $\{i_r\}$ to $S_{r-1}$.
	Given a subset $T \subseteq {\Omega}$, we define

	$\eta_r = \max_{i\in S^* \setminus S_{r-1}} \frac{g_T(S_{r-1} \cup \{i\})- g_T(S_{r-1})}{s_i}$
	for $1\leq r \leq \ell +1$
	(since $S^* \nsubseteq S$ the maximization is never over an empty set).
	By the definition of $\theta_r$ we have
	$g(S_r) = \sum_{j=1}^{r} \theta_j s_{i_j}$
	for
	$1\leq r \leq \ell$.
	If there is $1\leq r \leq \ell$ for which $\eta_r >\theta_r$,
	set $t = \min\{r| 1\leq r \leq \ell, \eta_r >\theta_r\}-1$, otherwise
	set $t = \ell$.

	Let $i^* \in S^* \setminus S_t$ such that $\eta_{t+1} = \frac{g_T(S_t \cup \{i^*\})- g_T(S_t)}{s_{i^*}}$ (one exists by the definition of $\eta_r$). If $t<\ell$, by the
	submodularity of $g$ we have that
	$\frac{g_{S_t}(\{i^*\})}{s_i} \geq \eta_{t+1} > \theta_{t+1}$; therefore
	in the iteration of {\sc Greedy} in which $i_{t+1}$ was added to $S$, it holds that $i^* \notin E$ (otherwise
	it would have been selected instead of $i_{t+1}$), and we can conclude
	that $s(S_t)+ s_{i^*} > m'$. If $t=\ell$, we know that by the end of
	the execution of {\sc Greedy} $i^* \notin E$, therefore $s(S_t)+ s_{i^*} > m'$ as well.

	Define $m_r =s(S_r)$ for $0\leq r \leq t$ and  $m_{t+1} = s(S_t) + s_{i^*}$. Also,
	define $p_j = \theta_r$ for $1\leq r \leq t$ and $j = m_{r-1} +1 , m_{r-1}+2, \ldots, m_r$,
	and $p_j = \eta_{t+1}$ for $j = m_t +1, m_t +2, \ldots, m_{t+1}$.
	Clearly, by the submodularity of $g$,

	it holds that $g_T(S_r)\leq g(S_r) = \sum_{j=1}^{m_r} p_j$, for $0 \leq r \leq t$.
	Also, it is easy to see that for any $0\leq r \leq  t$  we have $\eta_{r+1} \leq p_{m_r+1}$.

	The following sequence of inequalities follows from the above observation
	and the submodularity of $g$. For any $0\leq r \leq t$:
	\[
	\begin{array}{ll}
	g_T(S^*)   & \leq   g_T(S_r) + \sum_{i \in S^* \setminus S_r} \left(g_T(S_r \cup \{i\})-g_T(S_r) \right)  \\ \\
	& \leq   g_ T(S_r) + m^* \eta_{r+1}  \leq \sum_{j=1}^{m_r} p_j + m^* p_{m_r +1}
	\end{array}
	\]
	Therefore,
	\[
	\begin{array}{l}
	g_T(S^*) \leq \min_{1\leq r \leq t }\left\{\sum_{j=1}^{m_r} p_j + m^* p_{m_r +1}\right\}=
	\min_{1\leq s \leq m_{t+1} } \left\{ \sum_{j=1}^{s-1} p_j + m^* p_s\right\}
	\end{array}
	\]

	We now use inequality (4) in~\cite{S04}:

	\[
	\begin{array}{ll}
	\frac{g(S_t) + g_T(\{i^*\})}{g_T(S^*)}
	& \geq
	\frac{ \sum_{s=1}^{m_{t+1}} p_j } { \min_{1\leq s \leq m_{t+1} } \left\{ \sum_{j=1}^{s-1} p_j + m^* p_s\right\}} \\  \\
	& \geq
	(1-e^{m_{t+1}/m^*}) \geq (1-e^{m'/m^*}),
	\end{array}
	\]

	and the lemma follows immediately.
\end{proof}

\section{Approximation Algorithm}
\label{sec:approx_alg}

In this section we present an approximation algorithm for {\sf Group GAP}. We first introduce several definitions and tools that will be used as
building blocks of our algorithm.

\subsection{Basic Definitions and Tools}
\label{sec:tools}
\subsubsection{The Submodular Relaxation}
\label{sub_intro}

For simplicity, we assume that all the numbers are rational.
For a subset of elements $I' \subseteq I$, let $s(I')= \sum_{i\in I'} s_i$ be the total size of the elements in $I'$.
We assume throughout the discussion that every $G_\ell \in {\cal G}$
satisfies $s(G_\ell) \leq \frac{m}{2}$.
We define below a function ${\phi}: 2^I \rightarrow {\rm I\!R}^+\cup \{0\}$.
Let $x_{i,j} \in \{0,1\}$ be an indicator for the assignment of item $i$ to bin $j$, for $1 \leq i \leq n$, $1 \leq j \leq m$.
The following is a linear program associated with a subset $S \subseteq I$, in which $x_{i,j} \geq 0$ for all $i,j$.

\begin{alignat}{3}
LP(S)\text{:}&  \text{ maximize } &&\sum_{i\in I, j \in M} x_{i,j} \cdot p_{i,j} \nonumber\\
& \text{ subject to: } && \sum_{j \in M} x_{i,j}  \leq 1 && \forall{i\in I}  \label{select} \\
& && \sum_{i \in I} x_{i,j}  \cdot s_i \leq 1 && \forall{j \in M} \label{capacity} \\
& &&x_{i,j}=0 && \forall i \in I \setminus S, j \in M \nonumber \\
& && x_{i,j}\geq 0 && \forall i \in I, j \in M  \nonumber
\end{alignat}

Note that, by the above constraints, all solutions for the LP have the same dimension, regardless of the size of $S$.
We define ${\phi}(S)$ as the optimal value of $\mbox{LP}(S)$.

We denote the profit of a solution $x$ for the linear program by $p \cdot x = \sum_{i \in I, j \in M} x_{i,j} \cdot p_{i,j}$.
In Section~\ref{sec: submod} we prove the next result.

\begin{theorem}
	\label{sub}
	The function $\phi$ is submodular.
\end{theorem}

We note that $\phi$ is also monotone and non-negative. We use $\phi$ to define the {\em group function} $\psi: 2^{\cal G} \rightarrow {\rm I\!R}^+\cup \{0\}$. For any $G^* \subseteq {\cal G}$ let
$I(G^*) = \bigcup_{G_\ell \in G^*} G_\ell$ and
$\psi(G^*) = \phi(I(G^*) )$. As $\phi$ is submodular, monotone and non-negative, it is easy to see
that $\psi$ is submodular, monotone and non-negative as well.
We optimize $\psi$ subject to a knapsack (budget) constraint, using the next general result.

\begin{theorem} {\bf [Submodular optimization with reserved capacity]}
	\label{thm:halfsvi}
Let ${\Omega}= \{ 1, \ldots, n \}$ be a ground set,
and $m \geq 0$ a knapsack capacity.
Each $i \in {\Omega}$ is associated with non-negative size $s_i \leq \frac{m}{2}$. Let $f: 2^{\Omega} \rightarrow {\rm I\!R}^+\cup \{0\}$ be a  non-negative monotone submodular function,
and $\mbox{OPT} = \max \set{ f(S)| S\subseteq {\Omega}, \sum_{i\in S} s_i \leq m}$.
Then Algorithm \ref{alg:subds} (in Section \ref{sec:submod_optimize})
 finds in polynomial time\footnote{The explicit representation of a submodular function might be exponential in the size of its ground set. Thus, it is standard practice to assume that the function is accessed via a value oracle.
 Then the number of operations and oracle calls is polynomial in the size of ${\Omega}$ and the maximum length of the representation of $f(S)$.}
 a subset $S\subseteq {\Omega}$ satisfying
$f(S)\geq \frac{\mbox{OPT}}{3}$ and $\sum_{i\in S} s_i \leq \frac{m}{2}$.
\end{theorem}
The proof of Theorem \ref{thm:halfsvi} is given in Section~\ref{sec:submod_optimize}.
\subsubsection{Solution Types}

Our algorithm uses a few types of intermediate solutions for {\sf Group GAP}, as defined below.
Given $G^* \subseteq {\cal G}$, we say that a solution $x$ for $LP(I(G^*))$ is a {\em fractional solution}.
Let $U=(U_1,\ldots, U_m)$ be an assignment of elements to bins, where $U_j$ is the set of elements assigned to bin
$j$. Then $I(U) = \bigcup_{j=1}^{m} U_j$ is the subset of elements packed in the bins.
We say that $U$ is {\em feasible} if for each bin $1 \leq j \leq m$ we have $s(U_j) \leq 1$.
We say that $U$ is {\em almost feasible} if for each bin $1 \leq j \leq m$ there is an element $u_j^*$ such
that $s(U_j \setminus \set{u_j^*}) \leq 1$. We also define the profit of an assignment as
$p(U) = \sum_{1 \leq j \leq m} \sum_{i \in U_j} p_{i,j}$.

Our algorithm first obtains a fractional solution, which is then converted to an almost feasible solution. Finally, the algorithm converts this solution to a feasible one.
We now state the results used
in these conversion steps.

\begin{theorem}
	\label{thm:shmoys_trados}
	Given $G^* \subseteq {\cal G}$, such that $s(I(G^*))\leq m$,  and a fractional solution $x$ for $LP(I(G^*))$, it is possible to construct in
	polynomial time an almost feasible assignment $U$ such that $p(U) \geq p \cdot x$, and
	$I(U) = I(G^*)$.
\end{theorem}

The theorem easily follows by applying a rounding technique of~\cite{ST93} to a fractional solution
in which every element in $I(G^*)$ is fully assigned (fractionally, in multiple bins). We note that such a solution always exists, since
$s(I(G^*)) \leq m$.
We give the proof in the Appendix.
To convert an almost feasible solution to a feasible one we use the following result (we give the proof in Section \ref{filling_sec}).

\begin{theorem}
	\label{thm:filling}
Let $U=(U_1, \ldots, U_m)$ be an almost feasible assignment
such that $s(I(U)) \leq \frac{m}{2}$, then $U$ can be converted in
polynomial time to a feasible assignment $U'$, with $I(U') = I(U)$
and $p(U') \geq \frac{1}{2} p(U)$.
\end{theorem}

\subsection{The Algorithm}

Our approximation algorithm for {\sf Group GAP} follows easily from
the tools presented in Section \ref{sec:tools}. Initially, we solve the problem of maximizing a submodular function
subject to a knapsack with reserved capacity constraint for the set function $\psi$.
Then we solve the linear program and convert the
solution to a feasible assignment.
We give the pseudocode in Algorithm~\ref{alg:gg}.

\begin{algorithm}
	\caption{{\sf Group GAP} Algorithm}
	\label{alg:gg}
	\begin{algorithmic}[1]
		\State
		\label{step:submod_knapsack_constraint}
		Solve the
		submodular optimization problem:
		$\max_{ \{S\subseteq {\cal G}, \sum_{G_\ell \in S} s(G_\ell) \leq m/2 \}} \psi(S)$
		using  Algorithm \ref{alg:subds}. Let $S^*$ be the solution found.
		\State Find a (fractional) solution $x$ for $LP(I(S^*))$ that realizes $\psi(S^*)$.
     \State Use Theorem~\ref{thm:shmoys_trados} to convert $x$ to an almost feasible assignment $U$ with $I(U) = I(S^*)$.
		\label{step:round}
		\State  Use Theorem~\ref{thm:filling} to convert $U$ into a feasible solution; return this solution.
		\label{step:feasible}
	\end{algorithmic}
\end{algorithm}

\begin{theorem}
	\label{thm:ggap_appx_ratio}
 Algorithm \ref{alg:gg} is a polynomial time  $\frac{1}{6}$-approximation algorithm for {\sf Group GAP}
 when the total size of a single group is bounded by $\frac{m}{2}$; that is, $\forall G_{\ell} \in {\cal G}: \sum_{i \in G_{\ell} }s_i \leq \frac{m}{2} $.
\end{theorem}

\begin{proof}

It is easy to see that the algorithm runs in polynomial time.
By Theorem \ref{thm:halfsvi}, we have that $\psi(S^*)\geq \mbox{OPT} /3$, where $\mbox{OPT}$ is the
value of the optimal solution for the original instance.

By Theorems \ref{thm:shmoys_trados} and \ref{thm:filling}, we are guaranteed to find in Steps~\ref{step:round}$-$\ref{step:feasible} a feasible assignment $U$ of all elements in $I(S^*)$,
such that $p(U) \geq \frac{1}{2} \psi(S^*) \geq \frac{1}{6} \mbox{OPT}$.
\end{proof}

\section{Discussion and Future Work}

In this paper we presented a $\frac{1}{6}$-approximation algorithm for {\sf Group GAP}, using  a mild restriction
 on group sizes. A key component in our result is
an algorithm for submodular maximization subject to a knapsack constraint,
which finds a solution occupying
at most half the knapsack capacity, while the other half is {\em reserved} for later use.
Our results leave several avenues for future work.

As mentioned above, {\sf Group GAP} with no assumption on group sizes cannot be
approximated within any constant factor.
Yet, the maximum group size that still allows to obtain a
constant ratio can be anywhere in $[\frac{m}{2}, \frac{2}{3}m]$.
A natural question is whether our results can be applied to instances with larger group sizes. We note that the ratio stated in Theorem~\ref{thm:ggap_appx_ratio}
may not hold already for instances in which group sizes can be at most $\frac{m}{2}(1 + \varepsilon)$, for some $\varepsilon >0$. Indeed, for such instances,
it may be the case that no set of groups of total size at most $m/2$ is `good' relative to the optimum.
The existence of an algorithm that yields a constant ratio for such instances remains open.

While our result for submodular optimization with reserved capacity (Theorem \ref{thm:halfsvi}) gives an optimal approximation ratio for the studied subclass of instances, we believe the result
can be extended to other subclasses. In particular, we conjecture that for instances where each item is of size at most $\delta>0$, the approximation ratio approaches
$1-e^{-\frac{1}{2}}$ as $\delta \rightarrow 0$.
Such result would yield improved the approximation ratio for instances of {\sf Group GAP} in which the total size of each
group is bounded by $\delta m$. We defer this line of work to the full version of the paper.

Lastly, we introduced in the paper the novel approach of submodular optimization subject to a knapsack with reserved capacity constraint. We applied the approach along with
a framework similar to the one developed in \cite{AF+16}. It is natural
to ask whether the approach can be used to improve the approximation ratio
obtained in \cite{AF+16} for {\em all-or-nothing} {\sf GAP}.

\section{Filling Phase}
\label{filling_sec}

In this section we prove Theorem~\ref{thm:filling}.
Define the {size of bin} $j$ in assignment $U$ as  $s^U_j = \sum_{i\in U_j} s_i$.
We first divide the bins and items into types.
We say that a bin $j$ is {\em full}  if $s^U_j > 1$, {\em semi-full} if $ \frac{1}{2} \leq s^U_j \leq 1$, and
{\em semi-vacant} if $s^U_j < \frac{1}{2}$.
An item $i \in I(U)$ is {\em big} if $s_i > \frac{1}{2}$; otherwise,
$i$ is {\em small}. Clearly, there are no big items in semi-vacant bins.

Informally, we use in the proof several types of resolution steps. Each step takes as input
a full bin and possibly one or two semi-vacant bins, and reassigns some of the items into the bins while evicting others.
These resolution steps ensure that the new assignment has at least half the profit of the original assignment, the assignment to any bin remains feasible, and only small items
are evicted.

We apply the resolution steps repeatedly,  but once a bin participated
in a resolution step it may not participate in another one.
We then prove that as long as there are full bins, one of the steps can be
applied. Hence, by applying the resolution steps, we have a new
assignment in which all bins are feasible, and the total profit is at
least half the profit of the original assignment.
To handle the evicted items, we note that
as $s(I(U))\leq m/2$  and all the evicted items are small, it
is possible to assign the evicted items to bins without
violating the capacity constraints.

\bigskip

\noindent
{\bf Proof of Theorem~\ref{thm:filling}:}
For any bin $1 \leq j \leq m$ and $A \subseteq I$, let $p_j(A)  = \sum_{i\in A} p_{i,j}$ be
the total profit gained from packing $A$ into $j$.
The first step is to resolve the violation of the capacity
constraint in each full bin. We do that using four types of
resolution steps. Each step takes a full bin and possibly one or two semi-vacant bins,
modifies their contents and adds some small elements to a set $V$ of {\em evicted}
elements, that will be handled later. Throughout the discussion, we consider for a full bin $j$ a partition of the elements in $U_j$ into
two feasible subsets, given by $\set{A_j,B_j}$. We use the following resolution steps.

\begin{enumerate}
	\item
	\label{nobig}
	Consider a full bin $j$ such that $U_j$ has no big elements.

	If $p_j(A_j) > p_j(B_j)$ then set $U'_j = A_j$ and evict $B_j$ ($V : = V \cup B_j$);
	otherwise, set $U'_j = B_j$ and evict $A_j$, i.e., $V : =V \cup A_j$.
	In both cases $U'_j$ is feasible and $p_j(U'_j) \geq \frac{1}{2} \cdot p_j(U_j)$.
	\item
	\label{one_big}
	Now, suppose we have a full bin $j$ such that $U_j$ has a single big element, and
	a semi-vacant bin $\ell$.
	Let $\set{A^*, B^*} = \set{A_j,B_j}$, such that the big element is in $A^*$.

	If $p_j(A^*) +p_\ell(U_\ell) > p_j(B^*)$, set $U'_j = A^*$, $U'_\ell= U_\ell$
	and evict the elements in $B^*$ ($V := V \cup B^*$). We note that in this
	case $p_j(U'_j) + p_\ell(U'_\ell) = p_j(A^*) +p_\ell(U_\ell)$.

	Otherwise, set $U'_j = B^*$ and $U'_\ell= A^*$, and evict all the elements
	in $U_\ell$, i.e., $V := V \cup U_\ell$. In this case we have
	$p_j(U'_j) + p_\ell(U'_\ell) \geq p_j(B^*)$.

	Therefore, in both cases have  $p_j(U'_j) + p_\ell(U'_\ell) \geq \frac{1}{2} \cdot \left(p_j(U_j) + p_\ell(U_\ell)\right).$

	\item \label{two_big}
	Consider a full bin $j$ such that $U_j$ has two big elements, and
	a semi-vacant bin $\ell$, such that one of the big elements has space
	in bin $\ell$; that is, there is a big element $i^* \in U_j$ such that
	$s_{i^*} + s^U_{\ell} \leq 1$.

	Let  $\set{A^*, B^*} = \{ A_j,B_j \}$ such that $i^*\in A^*$.  We note that
	there cannot be any other big element in $A^*$ other that $i^*$.

	If $p_j(B^*) + p_\ell(U_\ell) > p_j(A^*)$ set  $U'_j = B^*$ and
	$U'_\ell = U_\ell \cup \set{i^*}$ (note that $s^{U'}_{\ell} \leq 1$). Also,
	evict all elements in $A^* \setminus \set{i^*}$.
	In this case we have $p_j(U'_j) + p_\ell(U'_\ell) \geq p_j(B^*)+ p_\ell(U_\ell)$.

	Otherwise, we set $U'_j = A^*$ and $U'_\ell = B^*$, and evict
	$U_\ell$ ($V := V \cup U_\ell$). In this case we have
	$p_j(U'_j) + p_\ell(U'_\ell) \geq p_j(A^*)$.

	Thus, in both cases
	$p_j(U'_j) + p_\ell(U'_\ell) \geq \frac{1}{2} \cdot \left(p_j(U_j) + p_\ell(U_\ell)\right).$

	\item \label{last_resort}
	Finally, consider a full bin $j$, such that $U_j$ has two big elements, and
	two semi-vacant bins $\ell_1$ and $\ell_2$.
	Recall $A_j,B_j$ is a partition of the elements in $U_j$ into two feasible subsets.

	If $p_j(A_j)  + p_{\ell_1}  (U_{\ell_1})> p_j(B_j) + p_{\ell_2} ( U_{\ell_2})$,
	set $U'_j = A_j$ , $U'_{\ell_1} = U_{\ell_1}$  and $U'_{\ell_2} = B_j$, and
	evict $U_{\ell_2}$.  Thus, we have
	$$p_j(U'_j) + p_{\ell_1}(U'_{\ell_1}) + p_{\ell_2}(U'_{\ell_2}) \geq
	p_j(A_j) + p_{\ell_1} ( U_{\ell_1}).$$

	Otherwise, set $U'_j = B_j$, $U'_{\ell_1} = A_j$ and $U'_{\ell_2} = U_{\ell_2}$ and evict
	$U_{\ell_1}$. Here $$p_j(U'_j) + p_{\ell_1}(U'_{\ell_1}) + p_{\ell_2}(U'_{\ell_2}) \geq
	p_j(B_j) + p_{\ell_2} ( U_{\ell_2}).$$

	And finally, we always have
	\[p_j(U'_j) + p_{\ell_1}(U'_{\ell_1}) + p_{\ell_2}(U'_{\ell_2}) \geq
	\frac{1}{2} \cdot \left(  p_j(U_j) + p_{\ell_1}(U_{\ell_1}) + p_{\ell_2}(U_{\ell_2})  \right) .
	\]

\end{enumerate}

Each time we execute a step we mark the bins used in this step
as {\em resolved}, and we do not consider them in the next steps.
We first use Steps \ref{nobig},\ref{one_big}, and \ref{two_big}, until none of them can
be applied.

Consider the average size of the unresolved bins.
When we start, there are $m$ bins of average size no greater than half.
Each of Steps  \ref{nobig},\ref{one_big}, \ref{two_big}  reduces
the size of the unresolved bins by at least one (as a full bin is removed)
and reduces the number of bins by at most two. Therefore, the
average size of the unresolved bins remains no more than half.
Also, marking all the semi-full bins as resolved  preserves the property.

Let $a$ be the number of unresolved full bins  and $c$ be the number of
unresolved semi-vacant bins.  Due to the average size of bins,
we have $a \leq \frac{a+c}{2}$, therefore $a \leq c$.
Hence, if we have a full bin, there must be a semi-vacant bin as well.
As we used Steps \ref{nobig},\ref{one_big}, \ref{two_big}  to exhaustion,
every full bin must have two big elements (no bin in $U$ contains more than two big elements),
and none of these big elements can fit into
one of the semi-vacant bins.

Denote the minimal size of a semi-vacant unresolved bin by $r$. Then
each of the full bins has two big elements of size greater than $1-r$.
Hence, we have
$c\cdot r + 2  a \cdot ( 1-r) < \frac{a+c}{2}$,
which leads to
$ 2 a(1-r) - \frac{a}{2}  < c\left(\frac{1}{2} - r \right)$,
and

\[
\begin{array}{ll}
c &  > a \cdot \displaystyle{\frac{2-2r - \frac{1}{2}}{\frac{1}{2} -r }=
	a \cdot \frac{3-4r  }{1 -2r }} \\
\\
& = \displaystyle{
	a \cdot \left( \frac{2-4r}{1-2r} + \frac{1}{1-2r}\right) =
	a \cdot \left( 2+ \frac{1}{1-2r}\right)  > 2a},
\end{array}
\]
implying that we can now run Step \ref{last_resort}, until there are no more
unresolved full bins.

We use the resolution steps to eliminate all the full bins. Every time
we run such a step over a set of bins we lose at most half the profit of
the bins participating in the step.
As the total size of items in the assignment is bounded by $m/2$, we
are guaranteed that it is possible to assign all the evicted elements to some
bins.
Thus, we are able to resolve the capacity overflow while losing at most
half of the profit. \hfill \qed

\section{#1}\vspace{-0.05in}}
\newcommand{\mysubsection}[1]{\vspace{-0.05in}\subsection{#1}\vspace{-0.05in}}
\newcommand{\mysubsubsection}[1]{\vspace{-0.1in}\subsubsection{#1}\vspace{-0.05in}}
\newcommand{\myparagraph}[1]{\par\smallskip\par\noindent{\bf{}#1:~}}

\usepackage{amssymb}
\newtheorem{duplicate}{Theorem}

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}

\newcommand{\mbox{LP}}{\mbox{LP}}
\newcommand{\mbox{sol}}{\mbox{sol}}
\newcommand{\mbox{empty}}{\mbox{empty}}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\varepsilon}{\varepsilon}
\newcommand{\remove}[1]{}
\newcommand{\tilde{E}}{\tilde{E}}
\newcommand{\mbox{OPT}}{\mbox{OPT}}
\newcommand{Group \sc gap}{\sc ggap}
\newcommand{\cal G}{\cal G}
\newcommand{\Omega}{\Omega}
\newcommand{\phi}{\phi}
\newcommand{\eta}{\eta}
\newcommand{\psi}{\psi}
\newcommand{\cal A}{\cal A}
\newcommand{\sf Group GAP}{\sf Group GAP}
\newcommand{\sf GAP}{\sf GAP}
\newcommand{\rm I\!R}{\rm I\!R}
\newcommand{\mathbb{Z}}{\mathbb{Z}}
\newcommand{{\hat s}_i}{{\hat s}_i}
\newenvironment{dl_proof}[1]{\vspace{\baselineskip}\noindent{\bf Proof of Lemma #1:}}{
	\hspace*{\fill}{\qed}}
\newenvironment{dl_claim_proof}[1]{\vspace{\baselineskip}\noindent{\bf Proof of Claim #1:}}{
	\hspace*{\fill}{\qed}}
\newenvironment{dl_thm_proof}[1]{\vspace{\baselineskip}\noindent{\bf Proof of Theorem #1:}}{
	\hspace*{\fill}{\qed}}

\begin{document}

\maketitle

 \input{abstract}
\clearpage
\pagenumbering{arabic}
\input{intro}
\input{approx_algorithm}
\input{submod}
\input{submod_optimize}
\input{filling}
\input{discussion}

\section{Introduction}
\label{sec:intro}

With the rapid adoption of cloud computing, wireless networks, and other modern platforms, resource
allocation problems of various flavors have regained importance. One
classic
example is the {\em generalized assignment problem} ({\sf GAP}).
We are given a set of $n$ items and $m$ bins, $[m]=\{1, 2, \ldots , m\}$. Each item
 $i\in [n]$ has a size $s_{i,j} > 0$ and a profit $p_{i,j} \geq 0$ when packed into bin $j \in [m]$.
 The goal is to feasibly pack in the bins a subset of the items
of maximum total profit.
{\sf GAP} has been widely studied, with applications ranging from
grouping and loading for manufacturing systems to  land use optimization in
regional planning
(see, e.g., \cite{B76,CH99}). In discrete optimization, {\sf GAP}
has received considerable attention
also as  a special
case of the {\em separable assignment} problem  and
 {\em submodular maximization}~(see, e.g., \cite{V08,FGMS11,BTW15,BF16}).
We consider a
variant of {\sf GAP} with group constraints.
An instance of {\sf Group GAP} consists of
 a set $I=\{1,2, \ldots, n\}$ of $n$ items and $m$ uniform (unit-sized) bins $M=\{1, \ldots , m \}$. Each item $i \in I$ has a size $ s_i >0 $ and a profit
$p_{i,j} \geq 0$ when assigned to bin $1 \leq j \leq m$.
The items in $I$ are partitioned into $L \geq 1$ groups,  ${\cal G} = \{ G_1, \ldots, G_L \}$.
Given an assignment of items to bins, we say that a group is {\em satisfied} if all of
its items are assigned.
The goal is to find a feasible assignment of a subset of the items to bins
such that the total profit from satisfied groups is maximized.
Formally, a feasible assignment is a tuple $(U_1, \ldots , U_m)$, such that $U_j \cap U_k = \emptyset$ for all $1 \leq j < k \leq m$,
$U_j \subseteq I$ and $\sum_{i \in U_j} s_i \leq 1$, for all $1 \leq j \leq m$. Let $I(U) = \cup_j U_j$. Then $G_\ell \in {\cal G}$ is satisfied if $G_\ell \subseteq I(U)$.
Let ${\cal G}_s = \{ G_{\ell_1}, \ldots G_{\ell_t} \}$ be the set of satisfied groups and $I({\cal G}_s) = \cup_{G_\ell \in {\cal G}_s } G_\ell$.
Then we seek an assignment $(U_1, \ldots , U_m)$ for which $\sum_{j=1}^m \sum_{i \in U_j \cap I({\cal G}_s )} p_{i,j}$ is maximized.

The following scenario suggests a natural application for
{\sf Group GAP}. Consider a Video-on-Demand (VoD) service where each  video is given as a collection of segments.
The system has a set of $m$ servers of uniform capacity
distributed over multiple locations.
To obtain revenue from a video the system must store
all of its segments (possibly  on different  servers). The revenue from a specific
video also depends on the servers which store  the
segments. This is  due to the content delivery costs
resulting from the distance between
the servers  and the predicted location
of the video audience. The objective of the
VoD service provider is to select a subset of segments
and an allocation of these segments to servers so as to maximize the total revenue.
In the Appendix we describe central applications of {\sf Group GAP} in
mobile Device-to-Device network caching and in base station cooperation in 5G networks.

\mysubsection{Prior Work}
\label{sec:prior_work}

We note that a {\sf Group GAP} instance in which each group consists of a {\em single}
item yields an instance of classic {\sf GAP} where each item takes a single size
across the bins, and all the bins have identical capacities.
{\sf GAP} is known to be APX-hard already in this case, even if there  are only two possible item sizes, and
each item can take one of two possible profits~\cite{ck00}.
Thus, most of the previous research focused on obtaining
efficient approximate solutions.\footnote{Given an algorithm ${\cal A}$, let ${\cal A}(I),OPT(I)$ denote the
	profit of the solution output by ${\cal A}$ and by an optimal solution for a problem instance $I$, respectively.
	For $\rho \in (0,1]$, we say that
	${\cal A}$ is a $\rho$-approximation algorithm if, for any instance $I$, $\frac{{\cal A}(I)}{OPT(I)} \geq \rho$.}
Fleischer et al.~\cite{FGMS11} obtained a $(1 - e^{-1})$-approximation
for {\sf GAP}, as a special case of the {\em separable assignment problem}.
Feige and Vondr{\'a}k~\cite{FV06} obtained the current best known ratio of $1 - e^{-1}+\varepsilon$, for some absolute constant $\varepsilon >0$.

Chen and Zhang~\cite{CZ16} studied the problem of {\em group packing of items into multiple knapsacks} ({\sf GMKP}), a
 special case of {\sf Group GAP} where
the profit of each item is the same across the bins.
Let {\sf GMKP}$(\delta)$ be
the restriction of {\sf GMPK} to instances in which the total size of items in each group is at most $\delta m$ (that is, a factor $\delta$ of the total capacity of all bins).
For $\delta >\frac{2}{3}$, the paper~\cite{CZ16} rules out the existence of a constant factor approximation for {\sf GMKP}$(\delta)$, unless {\sf P}= {\sf NP}.
For $\frac{1}{3}<\delta \leq \frac{2}{3}$, the authors show that there is no
$\left(\frac{1}{2} +\varepsilon\right)$-approximation for  {\sf GMKP}$(\delta)$, unless {\sf P}= {\sf NP}, and derive a nearly matching $\left(\frac{1}{2}- \varepsilon\right)$-approximation, for any $\varepsilon >0$.
The paper presents also approximation algorithms and hardness results for other special cases of {\sf GMPK}.

There has been earlier work also on variants of {\sf Group GAP}
with the added constraint that
in any feasible assignment there is at most one item from $G_\ell$ in bin $j$, for any
$1 \leq \ell \leq L$, $1 \leq j \leq m$. Adany et al.~\cite{AF+16} considered this problem,
called {\em all-or-nothing} {\sf GAP} {\sf (AGAP}). They presented
a $(\frac{1}{19} - \varepsilon)$-approximation algorithm for general instances, and a
$(\frac{1}{3} -\varepsilon)$-approximation for the special case where the profit of an item is identical across the bins, called the {\em group packing} ({\sf GP}) problem.
Sarpatwar et al.~\cite{SSS18} consider a more general setting for {\sf AGAP}, where each group of items is associated with a time window in which it can be packed.
The paper shows that this variant of the problem, called $\chi$-{\sf AGAP}, admits an $\Omega(1)$-approximation, assuming the time windows are large enough relative
to group sizes. Specifically, for a group $G_\ell$ having a time window of $m$ slots (= $m$ bins), it is assumed that $s(G_\ell) \leq \frac{m}{20}$.

\subsubsection{Submodular Maximization}

Given a finite set $\Omega$, a function $f:2^{\Omega} \rightarrow \rm I\!R$
is {\em submodular} if for every $S,T \subseteq \Omega$ we have
\[f(S) + f(T) \geq f(S \cup T) + f(S\cap T).\]

An equivalent definition of submodularity refers to its diminishing returns:
$$f(S \cup \{ u \}) - f(S) \leq f(T \cup \{ u \} )- f(T),$$ for any $T \subseteq S \subseteq \Omega$, and $u \in \Omega \setminus S.$
A set function $f$ is {\em monotone} if for every $S\subseteq T \subseteq \Omega$
it holds that $f(S) \leq f(T)$.
Submodular functions arise naturally in a wide variety of optimization problems, ranging from
coverage problems and graph cut problems to {welfare problems}
(see~\cite{BF17} for a survey on submodular functions).
Submodular optimization under various constraints has been widely studied in the past four decades (see, e.g.,~\cite{S04, CCPV11, FNS11} and~\cite{BF17} and the references therein).

The problem of maximizing a monotone submodular function subject to a knapsack constraint is defined as follows. We are given an oracle to a  monotone, non-negative submodular function
$f:2^{\Omega} \rightarrow \mathbb{R}$.  Each element $i\in \Omega$  is associated with
a size $s_i \geq 0$. We are also given a capacity $B > 0$. The objective is to find
a subset $S\subseteq \Omega$ such that $\sum_{i \in S} s_i \leq B$ and
$f(S)$ is maximized. The best known result is a $(1 - e^{-1})$-approximation algorithm due to Sviridenko~\cite{S04}. The ratio of $(1-e^{-1})$ cannot be improved even
when $f$ is a coverage function and element sizes are
uniform, unless {\sf P}= {\sf NP}~\cite{Fe98}. A matching lower bound of $(1-e^{-1})$ is known also
for the oracle model with no complexity assumption~\cite{NW78}.

\mysubsection{Contribution and Techniques}
\label{sec:results}

Our main result is a $\frac{1}{6}$-approximation algorithm
for {\sf Group GAP} instances
where the total size of each group is at most $\frac{m}{2}$.
We note that when group sizes can be arbitrary in $(0, m]$, {\sf Group GAP} cannot be approximated within any bounded ratio, even if
item profits are identical across the bins,
and $m=2$, unless {\sf P}= {\sf NP}. Indeed, in this case, deciding whether a single group  of items of total size $2$ and total profit $1$ can be packed in the bins yields an instance of
{\sc Partition}, which is NP-complete~\cite{GJ79}.
Furthermore, even if group sizes are restricted to be no greater than $\delta m$, for some $\delta> \frac{2}{3}$, then {\sf Group GAP} still cannot be approximated within a constant factor,
as it generalizes {\sf GMKP}$(\delta)$, for which the paper~\cite{CZ16} shows hardness of approximation.
Similarly, as we consider in this paper a generalization of {\sf GMKP}$\left(\frac{1}{2}\right)$, it follows from~\cite{CZ16} that our problem cannot be approximated within ratio
better than $\frac{1}{2}$.

In solving {\sf Group GAP} we combine
the framework of Adany et al.~\cite{AF+16} with the rounding technique
of Shmoys and Tardos~\cite{ST93}. The framework of~\cite{AF+16} uses
submodular maximization to select a collection of groups for the solution.
It then finds a feasible assignment for the selected groups.

At the heart of our algorithm lies
an interesting derivation of a submodular
function from the classic LP formulation of
{\sf GAP}, which facilitates the construction of
a high profit solution utilizing
at most half the total bin capacity.
In particular, we give an algorithm for submodular maximization
subject to a knapsack constraint,
which finds a solution occupying
at most half the knapsack capacity,
while the other half is {\em reserved} for later use.\footnote{We assume throughout the discussion that
the size of each element is at most half the knapsack capacity.}
We show that this algorithm achieves an approximation ratio of $\frac{1}{3}$ relative to an optimal solution that may use the whole knapsack capacity.
We note that this ratio is tight.
Indeed, it is easy to construct an instance
for which the best solution with half the knapsack capacity has only $\frac{1}{3}$ the profit of the optimal solution with full knapsack capacity.
We also note that a naive application of the algorithm of Sviridenko~\cite{S04} with half the
knapsack capacity will only guarantee a
$\frac{1- e^{-1}}{3}\approx \frac{1}{4.7}$-approximation.

To obtain an integral solution, given a fractional assignment of the selected groups,
we apply the rounding technique of Shmoys and Tardos~\cite{ST93},
followed by a filling phase.
We show that if the total size of the items in the selected groups is
at most $\frac{m}{2}$, the rounding procedure yields a {\em feasible} assignment of the selected groups, whose profit is
at least half the value of the submodular function.
Our novel approach of submodular optimization
subject to a knapsack {\em with reserved capacity} constraint
may find applications in solving other group assignment problems.

\section{Submodular Optimization with Reserved Capacity}
\label{sec:submod_optimize}

In this section we prove Theorem~\ref{thm:halfsvi}. We start with some definitions and notation.
Assume we are given a ground set
${\Omega}  = \{ 1, \ldots, n \}$ and capacity $m > 0$, where  each element $i \in {\Omega}$ is associated with a non-negative size $s_i \leq \frac{m}{2}$.
For $S \subseteq {\Omega}$, let $s(S) = \sum_{i\in S} s_i$.
Also, for $S,T \subseteq {\Omega}$ let $f_S(T) = f(S\cup T) - f(S)$. We use throughout this section basic properties of
monotone submodular functions (see, e.g.,~\cite{BF17}).
\vspace{-0.05in}
\begin{algorithm}
	\caption{\sc SubmodularOpt}
	\label{alg:subds}

	\hspace*{\algorithmicindent} \noindent \textbf{Input:} A monotone submodular function $f:2^{\Omega}\rightarrow \mathbb{R}_+$,
	sizes $s_i \geq 0$ for all $i \in {\Omega}$, and capacity $m > 0$.

	\hspace*{\algorithmicindent} \noindent \textbf{Output:} A subset of elements $R \subseteq {\Omega}$ such that $s(R) \leq \frac{m}{2}$.

	\begin{algorithmic}[1]

		\Procedure{Greedy}{$g$, $m'$}
		\State Set $S= \emptyset$, $E={\Omega}$.
		\While {$E\setminus S \neq \emptyset$}
		\State
		Find
		$i = \argmax_{i \in E \setminus S}  \frac{g_S(\{i\})}{s_i}$
		\label{greedy:argmax}
		\If {$s(S)  + s_{i} \leq m'$}

		set $S = S \cup \{i\}$.
		\EndIf
		\State Set $E = E \setminus \{i\}$.

		\EndWhile
		\State Return $S$
		\EndProcedure

		\State
		Set $R= \emptyset$
		\For {every set  $S_e \subseteq {\Omega}$,

			$|S_e|\leq 6$}
		\For {every set $B\subseteq S_e$, $s(B)\leq m/2$}
		\State $T = \Call{Greedy}{f_{S_e}, m/2 - s(B)}$
		\If {$f(B \cup T)\geq f(R)}$

		Set $R = B \cup T$.
		\EndIf
		\EndFor
		\EndFor
		\State Return $R$
	\end{algorithmic}
\end{algorithm}

In the following we give an outline of an algorithm for maximizing a monotone submodular function $f$ subject to
a knapsack {\em with reserved capacity} constraint.
Specifically, assuming that the knapsack capacity is $m$ for some $m >0$, the algorithm solves the problem $\max_{ \{ S \subseteq {\Omega}: s(S) \leq \frac{m}{2}\} } f(S)$.
The algorithm, {\sc SubmodularOpt}, initially guesses the set of at most
six items of highest profits in some optimal solution (for the problem with knapsack capacity $m$),
and a subset of these profitable items, whose total size is at most $m/2$.
Then the algorithm calls a procedure which applies the Greedy approach as in~\cite{S04} to find the remaining items in the solution. We give a pseudocode of {\sc SubmodularOpt}
in Algorithm~\ref{alg:subds}.  It is important to note that while the algorithm produces
a solution of size at most $m/2$, the analysis compares this solution against an optimal solution of size at most $m$.

The next lemma, which plays a key role in our analysis,
follows from the technique  presented in \cite{S04}.

\begin{lemma}
\label{thm:svi}
Given the knapsack capacity $m > 0$, let $0 < m' \leq m^* \leq m$.
Let $S^* \subseteq {\Omega}$ be a non-empty subset of elements, such that $s(S^*) \leq m^*$. Also, let
$g: 2^{\Omega} \rightarrow \rm I\!R$
be a monotone submodular function satisfying $g(\emptyset)=0$,  and let $S=\Call{Greedy}{g,m'}$.
Then, there is an element $i^*\in S^*$ such that
$g(S)+g(\{i^*\})\geq (1-e^{m'/m^*}) g(S^*)$.
\end{lemma}

In the Appendix we prove a more general result (see Lemma~\ref{thm:alpha_greedy}).\footnote{The statement of Lemma~\ref{thm:svi} is obtained by taking in Lemma~\ref{thm:alpha_greedy}
$T=\emptyset$.}
In \cite{S04} the above lemma was applied in conjunction with a guessing phase, used to ensure the three most
profitable elements in an optimal solution are selected by the
algorithm, thus limiting the value of $g(\{i^*\})$
in the special case where $m'=m^*$.

Attempting to apply a similar approach in solving the problem with
{\em reserved} capacity, several difficulties arise.
The first one is that
the most profitable elements in {\em any} optimal solution may already
exceed the reduced capacity, and therefore cannot be added to the solution.
Another difficulty is that even if these elements do fit in the smaller knapsack,
one can easily come up with a scenario
in which it is better not to include them in the solution.

To overcome these difficulties we use the following main observation.
Given $P_k$, the set of $k=6$ most profitable elements
in an optimal solution\footnote{The value $k=6$ is derived from Lemma \ref{thm:sub_technical}.
	It may be possible to obtain the same approximation ratio using smaller values of $k$,

	leading to a more efficient algorithm.}, and  a partition of this set into two subsets $B_1, B_2$, each of size at most $m/2$, adding elements
to either $B_1$ or $B_2$ using the greedy procedure leads
to a solution
of value at least one third of
the value of an optimal solution. This observation comes into play
in Case 2.2 in the proof of Theorem~\ref{thm:halfsvi}.
The next technical lemma
is used to prove this observation (we give the proof below).

\begin{lemma}
	\label{thm:sub_technical}
	For $k=6$, $p_A, p_B, S_A, S_B \geq 0$ define
	$$h(p_A,p_B,S_A, S_B) = p_A+ (1-p_A-p_B) \left(1-e^{ - \frac{\frac{1}{2} - S_A}{1- S_A - S_B} }\right) -
	\frac{p_A+p_B} {k}.$$
	Then for $p_1, p_2, S_1, S_2$ such that $0\leq p_1, p_2 \leq \frac{1}{3}$ and $0\leq S_1, S_2 \leq \frac{1}{2}$
	it holds that
	$$\max\left( h(p_1, p_2, S_1, S_2), h(p_2, p_1, S_2, S_1)\right) \geq \frac{1}{3}.$$
\end{lemma}

Another main tool used in the proof of Theorem~\ref{thm:halfsvi} is a simple partitioning procedure.
It shows that $P_k$ can either be partitioned into two sets as
required in the above observation, or we reach a simple corner case (Case 2.1 in the proof) in which at least one third of the optimal value can be easily attained. For the latter case, we use
the following result, due to~\cite{LB10}.

\begin{lemma}
	\label{thm:lin}
	Let $g: 2^{\Omega}\rightarrow \rm I\!R$ be a
	non-negative and monotone submodular function.
	Let $\mbox{OPT} = \max \set{ g(S)| S\subseteq {\Omega}, \sum_{i\in S} s_i \leq m}$, and $S=\Call{Greedy}{g, m}$. Then either $g(S) \geq (1-e^{-1/2}) \mbox{OPT}$,
	or there is an element $i\in {\Omega}$ such that $g(\{i\})\geq (1-e^{-1/2})OPT$ and $s_i \leq m$.
\end{lemma}

\noindent
{\bf Proof of Theorem \ref{thm:halfsvi} [Submodular optimization with reserved capacity]:}
It is easy to see that the running time of the algorithm is polynomial.
Let $S \subseteq {\Omega}$, $s(S)\leq m$, $f(S)= \mbox{OPT}$, and $k=6$.

\noindent
{\bf \underline {Case 1:}}
	We first handle the case where $|S| < k$.

	Start with $A_1 = \emptyset$, iterate over the elements of
	$S$ and add them to $A_1$, as long as $s(A_1) \leq m/2$.
	If $S\neq A_1$, let $j\in S\setminus A_1$, and set $A_2= \{j\}$
	and $A_3 =S \setminus (A_1 \cup A_2)$.  Clearly, $s(A_2 ) \leq m/2$,
	and since $s(A_1 \cup A_2 ) > m/2$ and $s(S)\leq m$, we have that $s(A_3)\leq m/2$.
	If $S = A_1$  set  $A_2 = A_3 =\emptyset$.

	By the submodularity of $f$, we have $f(S)\leq f(A_1) + f(A_2) + f(A_3)$. Hence,
	for some $r\in \{1,2,3\}$, $f(A_r) \geq f(S)/3=\mbox{OPT}/3$.  We also have
	that $|A_r| \leq 5$; therefore, at some iteration of the algorithm $S_e =B=A_r$, and following this iteration $f(R)\geq \mbox{OPT}/3$.

\noindent
{\bf \underline{Case 2:}}

	Assume now that $|S| \geq k$. Let $S= \{i_1, i_2, \ldots, i_\ell\}$ such that the
	elements are ordered by their marginal profits:
	$i_j = \argmax_{j\leq r \leq \ell} f_{\{i_1, \ldots i_{j-1}\}}(\{i_r\})$. Set
	$P_k = \{i_1, i_2, \ldots , i_k\}$.

	Consider the following process.  Start with $B_1 = \emptyset$ and $B_2 = \emptyset$. Iterate over the elements $i\in P_k$ in decreasing order by size. For each element $i$, let $t = \argmin_{j=1,2} s(B_j)$.
	If $s(B_t)+s_{i} \leq m/2$ then $B_t = B_t \cup \{i\}$;  otherwise, Stop.
	We now distinguish between two sub-cases for the termination of the process.

\noindent
{\bf \underline{Case 2.1:}}
		Suppose that the process terminates due to an element $i$ which cannot be added to any of the sets.
		Let $B_1$ and $B_2$ be the sets  in this iteration. Also, set $B_3 = \{i\}$, $U= B_1 \cup B_2 \cup B_3$,
		and $L = S\setminus U$. W.l.o.g assume that $s(B_1) \geq s(B_2)$.
		As the process terminated, we have that $s(B_3)+s(B_2) = s_i + s(B_2) >m/2$. The sets
		$B_1, B_2, B_3$ and $L$  form a partition of  $S$, and $s(S)\leq m$.
		We conclude that $s(B_1) + s(L) \leq m/2$.
		Hence, $s(B_2) +s(L) \leq m/2$, and $s(B_3) + s(L) \leq m/2$
		as well (it is easy to see that $s(B_3)\leq s(B_1)$).

		By the submodularity of $f$, $f(U)\leq f(B_1)+f(B_2) +f(B_3)$; thus,
		there is $j\in\{1,2,3\}$ such that $f(B_j)\geq f(U)/3$.
		As none of the sets $B_1,B_2,B_3$ is empty, we have that $|B_j| \leq |P_k| -2=4$.

		Let $T = \Call{Greedy}{f_{U},m/2 - s(B_j)}$. By Lemma \ref{thm:lin}, either

		\[
		\begin{array}{c}f_{U} (T) \geq (1-e^{-1/2}) f_{U}(L) \geq f_{U}(L)/3,
		\end{array}
		\]
		or there is $i\in L$ such that
		\[
		\begin{array}{c}f_{U} (\{i\}) \geq (1-e^{-1/2}) f_{U}(L) \geq f_{U}(L)/3.
		\end{array}
		\]

		In the former case, we can consider the iteration in which
		$S_e =U, B=B_j$. In this iteration, we have  $$f(B \cup T) \geq f(B_j) + f_{U}(T) \geq
		\frac{1}{3} ( f(U)+ f_U(L)) = \frac{1}{3}\mbox{OPT}.$$
		In the latter case, we can consider the iteration where
		$S_e  = B=B_j \cup \{i\}$, and in which
		$$f(B \cup T) \geq f(B) \geq f(B_j) + f_{B_j} ( \{i\}) \geq f(B_j) + f_{U} ( \{i\}) \geq \frac{1}{3} \mbox{OPT}.$$

\noindent
{\bf \underline{Case 2.2:}}
		The process terminated with $B_1, B_2$  satisfying $B_1 \cup B_2= P_k$, and $s(B_1),s(B_2)\leq m/2$.

		Let $p_1 = f(B_1) /\mbox{OPT}$, $p_2 = (f(P_k)- f(B_1)) /\mbox{OPT}$, $S_1 = s(B_1)$, $S_2 = s(B_2)$ and $L = S\setminus P_k$.
		If $p_1\geq \frac{1}{3}$ (or $p_2 \geq \frac{1}{3}$ ) we have that in the iteration
		where $S_e= P_k$  and $B=B_1$ (or $B = B_2$) the algorithm finds a solution of value at least
		$\mbox{OPT}/3$, and the theorem holds. Thus, we may
		assume that $p_1, p_2 \leq \frac{1}{3}$.

		For $j=1,2$, let $T_i = \Call{Greedy}{f_{P_k} , m/2-S_j}$. Using
		Lemma \ref{thm:svi} with $S^* = L$,
		we have that there is $i_j\in L$  for which
		$$f_{P_k}(T_j)+f_{P_k}(\{i_j\}) \geq  (1-e^{-\frac{\frac{1}{2}- S_j}{ 1- S_1 - S_2}}) f_{P_k} (L).$$
		By the selection of elements in $P_k$, we have
		$f_{P_k}(\{i_j\})\leq \frac{1}{k} f(P_k)$. Thus,
		$$f_{B_j}(T_j)\geq f_{P_k}(T_j)\geq  (1-e^{-\frac{\frac{1}{2}- S_j}{ 1- S_1 - S_2}}) f_{P_k} (L) - \frac{1}{k} f(P_k).$$
		Hence, in the iteration where $S_e = P_k, B=B_j$, we obtain a solution satisfying
		\[
		\begin{array}{ll}
		f(S_e\cup T) & = f(B_j \cup T_j) \geq
		f(B_j) + (1-e^{-\frac{ \frac{1}{2} - S_j}{1-S_1 -S_2 }}) f_{P_k} (L) - \frac{1}{k} f(P_k) \\ \\
	   & \geq \displaystyle{ \mbox{OPT} \left( p_j +(1-p_1+p_2) (1-\exp( -\frac{ \frac{1}{2} - S_j}{1-S_1 -S_2 } ) ) - \frac{p_1+p_2}{k}\right).}
		\end{array}
		\]
		By Lemma \ref{thm:sub_technical},
		in one of these iterations we obtain a solution of value at least $\mbox{OPT}/3$, implying the statement of the theorem. \hfill \qed

\bigskip
\noindent
{\bf Proof of Lemma \ref{thm:sub_technical}:}
Let $p_1, p_2, S_1, S_2$ be values that satisfy the conditions in the lemma.
Denote $p = p_1 + p_2$, $d= p_1 - p_2$ and $r = \exp\left(-\frac{\frac{1}{2} - S_1} {1 -S_1 -S_2}\right)$.
It is easy to see that $\exp\left(-\frac{\frac{1}{2} - S_2} {1 -S_1 -S_2}\right) = \frac{e^{-1}}{r}$.
Define $V_1 = h(p_1, p_2, S_1, S_2)$ and $V_2 = h(p_2, p_1, S_2, S_1)$.  By the definition of $h$ and above
definitions we get
$$V_1 = \frac{p+d}{2} +(1-p)(1-r) - \frac{p}{k}$$
and
$$V_2 = \frac{p-d}{2} +(1-p)\left(1-\frac{e^{-1}}{r}\right) - \frac{p}{k}$$
Let $g_1(x) = \frac{p+d}{2} +(1-p)(1-x) - \frac{p}{k}$
and $g_2(x) = \frac{p-d}{2} +(1-p)\left(1-\frac{e^{-1}}{x}\right) - \frac{p}{k}$.
Clearly, $V_1 = g_1(r)$ and $V_2 = g_2(r)$. It is also easy to
see that $g_1$ is decreasing and $g_2$ is increasing (for $x>0$).
\begin{claim}
	It holds that $g_1(x^*) = g_2(x^*)$ where  $x^*= \frac{d + \sqrt{d^2 + 4e^{-1} (1-p)^2}}{2(1-p)}$.

\end{claim}
\begin{proof}
	By rearranging terms we have  $g_1(x) = g_2(x)$
	if and only if $d = (1-p) ( x -\frac{e^{-1}}{x})$, which holds
	for $x>0$ if and only if
	$0 = (1-p) x^2 -dx -e^{-1}(1-p)$. The latter is a quadratic
	equation and $x^*>0$ is a root.
\end{proof}

If $r\geq x^*$, since $g_2$ is increasing, we have $V_2 = g_2(r) \geq g_2(x^*) = g_1(x^*)$, and if $r\leq x^*$, as $g_1$ is decreasing, we have $V_1 = g_1(r) \geq g_1(x^*)$. Therefore $\max (V_1, V_2) \geq g_1(x^*)$.

Consider two cases:

\noindent
{\bf Case 1:} $p\leq \frac{1}{3}$. We have $|d|\leq p$  and
$$g_1(x^*) = 1-\frac{p}{2} -\frac{\sqrt{d^2 + 4e^{-1}(1-p)^2}}{2} - \frac{p}{k} \geq 1-  \frac{p}{2} - \frac{p}{k} - \frac{\sqrt{p^2 + 4e^{-1}(1-p)^2}}{2}.$$

Let $a(y) = 1- \frac{y}{2} - \frac{y}{k} - \frac{\sqrt{y^2 + 4e^{-1}(1-y)^2}}{2}$. Clearly, $g_1(x^*)\geq a(p)$.
We note that $a''(y)= -\frac{2e^{-1}} {( y^2+ 4e^{-1} (1-y)^2 )^{\frac{3}{2}}} $.
As $a''(y) < 0$, $a(y)$ does not have
a local minima in $[0, \frac{1}{3}]$. Thus as $p\in [0, \frac{1}{3}]$
we have $$g_1(x^*)\geq a(p) \geq \min\left( a(0), a\left(\frac{1}{3}\right)\right) = \min \left( 1-e^{-0.5}, \frac{5}{6}- \frac{1}{3k} -\frac{\sqrt{1+16e^{-1}}}{6}\right) \geq \frac{1}{3}$$

\noindent
{\bf Case 2:} $p\geq  \frac{1}{3}$, as $\frac{p+d}{2}, \frac{p-d}{2} \leq \frac{1}{3}$ we have that $|d| \leq \frac{2}{3}- p$. Therefore,
$$g_1(x^*) = 1-\frac{p}{2} -\frac{\sqrt{d^2 + 4e^{-1}(1-p)^2}}{2} - \frac{p}{k} \geq 1-  \frac{p}{2} - \frac{p}{k} - \frac{\sqrt{(\frac{2}{3}-p)^2 + 4e^{-1}(1-p)^2}}{2}$$
Let  $b(z) = 1- \frac{z}{2} - \frac{z}{k} - \frac{\sqrt{(\frac{2}{3} - z)^2 + 4e^{-1}(1-z)^2}}{2}$. Clearly, $g_1(x^*) \geq b(p)$.  We note
that $$b''(z) = -\frac{2e^{-1}}{9 \left( 4e^{-1}(1-z)^2 +(\frac{3}{2}-z )^2 \right) ^{\frac{3}{2}}}<0.$$
Thus,  $b(z)$ does not have a local minima in $[\frac{1}{3}, \frac{2}{3}]$. Hence, we have that $g_1(x^*) \geq b(p) \geq \min(b(\frac{1}{3}),b( \frac{2}{3})) \geq \frac{1}{3}$.

In both cases we get $g_1(x^*)\geq\frac{1}{3}$, and as $\max(V_1, V_2)\geq g_1(x^*)$, the lemma immediately follows.
\hfill \qed

\section{Submodularity}
\label{sec: submod}

In this section we show that the function $\phi$ is submodular. Our proof builds on
the useful relation of our problem to maximum weight bipartite matching.
Let $G=(A \cup B,E)$ be a bipartite (edge) weighted graph, where $|B| \geq |A|$. Assume that the graph is complete (by adding zero weight edges if needed). For $e \in E$, let $W(e)$ be the weight of edge $e$, and for $F\subseteq E$,
let $W(F)= \sum_{e\in F} W(e)$ be the total weight of edges in $F$.
For $S\subseteq A$, define $h(S)$ to be the value of the maximum weight matching in $G[S \cup B]$, the graph induced by $S\cup B$. We call $h$ the {\em partial maximum
weight matching function}. The next result was shown by Bar-Noy and Rabanca~\cite{BR16}.

\begin{theorem}
\label{thm:submod_bp_matching}
If the edge weights are non-negative then the function $h$ is (monotone) submodular.
\end{theorem}
We give a simpler proof in the Appendix.
We are now ready to prove our main result.

\noindent
{\bf Proof of Theorem~\ref{sub}:}
We first note that since all numbers are rational, for some $N \in {\mathbb{Z}}^+$, we can write $s_i=\frac{{\hat s}_i}{N}$, where ${{\hat s}_i} \in {\mathbb{Z}}^+$ for all $i \in I$.\footnote{Note that $N$, which may be
	arbitrarily large, is used just for the proof. Our algorithm does not rely on obtaining a solution (or an explicit formulation) for $M(S)$.}

Now, set the capacity of each bin $1 \leq j \leq m$ to be $b_j=N$, and let $0  \leq y_{i,j} \leq {{\hat s}_i}$ indicate the size of item $i$ assigned to bin $j$.
For a subset of items $S \subseteq I$, we now write the following linear program.

\begin{alignat}{3}
M(S)\text{:}&  \text{ maximize } &&\sum_{i\in I} \frac{1}{{\hat s}_i} \sum_{j \in M} y_{i,j} \cdot p_{i,j} \nonumber\\
& \text{ subject to: } && \sum_{j \in M} y_{i,j}  \leq {{\hat s}_i} && \forall{i\in I}  \label{itemsize_bound} \\
& && \sum_{i \in I} y_{i,j}  \leq N && \forall{j \in M} \label{bincapacity_bound} \\
& && y_{i,j}=0 && \forall i \in I \setminus S, j \in M \nonumber \\
& && y_{i,j} \geq 0 && \forall i \in I, j \in M  \nonumber
\end{alignat}
Indeed, Constraint (\ref{itemsize_bound}) ensures that the total size assigned for item $i$ over the bins is upper bounded by ${{\hat s}_i}$, and Constraint (\ref{bincapacity_bound})
guarantees that the capacity constraint is satisfied for all the bins $j \in M$.
Given a subset of elements $S \subseteq I$,
let ${\eta}(S)$ be the value of an optimal solution for $M(S)$.

Now, observe that any feasible solution for $LP(S)$ induces a feasible solution for $M(S)$ of the same value, by setting
$y_{i,j}= x_{i,j} \cdot {{\hat s}_i}$ for all $i \in I$ and $j \in M$. Similarly, a feasible solution for $M(S)$ induces a feasible solution for $LP(S)$ of the same value.
Hence, $\phi(S) = {\eta}(S)$ for all $S \subseteq I$.

By the above discussion, to prove the theorem it suffices to show that ${\eta}$
 is submodular. Given our {\sf Group GAP} instance, we construct the following bipartite graph $G$. For each item $i \in I$, we define ${{\hat s}_i}$ vertices,
 $V_i = \{ v_{i,1}, \ldots , v_{i, {{\hat s}_i}} \}$. For each bin $j \in M$, we define $N$ vertices $U_j = \{ u_{j,1}, \ldots , u_{j,N} \}$. For any $1 \leq i \leq n$ and $1 \leq j \leq m$, there are
 edges $(v_{i,s}, u_{j,r})$ of weight $p_{i,j}/{{\hat s}_i}$, for all $1 \leq s \leq {{\hat s}_i}$, $1 \leq r \leq N$. Let $V_I = \cup_{i \in I} V_i$, $U_M = \cup_{j \in M} U_j$, and
 let $E$ be the set of edges.
 Consider the bipartite graph $G=(V_I \cup U_M, E)$. W.l.o.g we may assume that $|U_M| \geq |V_I|$; otherwise, we can add new bins $j=m+1, m+2, \ldots$ with corresponding sets of vertices $U_j = \{ u_{j,1}, \ldots , u_{j,N} \}$ and zero weight edges $(v_{i,s}, u_{j,r})$ for all $1 \leq i \leq n$, $1 \leq s \leq {{\hat s}_i}$, $1 \leq r \leq N$.

 We note that, given a subset of items $S \subseteq I$, $M(S)$ is the linear programming relaxation of the problem of finding a maximum weight matching in the
 subgraph $G[V_S \cup U_M]$,
 where $V_S \subseteq V_I$ is the subset of vertices in $G$ that corresponds to $S$.
 Using standard techniques (see, e.g.,~\cite{LRS11}), it can be shown that $M(S)$ has an optimal integral solution.

 Hence, ${\eta}(S)=h(V_S)$, where $h: 2^{V_I} \rightarrow {\rm I\!R}^+$ is a partial maximum weight matching function in $G$.
 By Theorem~\ref{thm:submod_bp_matching}, $h$ is (monotone) submodular.
 Hence, ${\eta}$ is also (monotone) submodular. 	\hfill \qed


\section{Introduction}

In the study of heat and other parabolic equations, one often
hopes to prove that solutions are real analytic in space and
time. While the spatial analyticity is usually
true for generic
solutions, the time analyticity is harder to prove
and is false in
general. For example, it is not difficult to construct a
solution of the heat equation in a finite space-time cylinder
in
the Euclidean setting, which is not time analytic in a sequence
of moments. On the other hand,
under extra assumptions, many time-analyticity
results for the heat equation can be found in the literature.
See, for example,  \cite{Wi:1}.  Moreover, if one imposes zero
boundary conditions on the lateral boundary of a smooth
cylindrical domain, then certain solutions of the heat,
Navier-Stokes, and many other parabolic equations are analytic
in time. See, for example, \cite{Ma:1}, \cite{Ko},
\cite{Gi:1}, and
\cite{EMZ:1}.  One can also consider solutions in certain $L_p$
spaces with $p \in (1, \infty)$. In this setting,
by using complexification argument the time
analyticity with values in an $L_2$-based Gevrey
class of periodic functions
was proved for the Navier-Stokes equations in
\cite{FT:1}. See also \cite{Pr} for an extension to
a large class of dissipative equations in the periodic
setting.

In a related development, there have been renewed interest in the
study of global solutions of the heat equation on the Euclidean
and manifold setting. One example is the study of ancient
solutions of the heat equation, i.e., solutions that exist in
the whole space and in all negative time. Let ${\bf M}=\mathbb R^d$ or a
complete noncompact Riemannian manifold with nonnegative Ricci
curvature.
In \cite{SZ:1}, it was found that sublinear ancient solutions
are constants.  Later in \cite{LZ:1}, it was shown that the
space of ancient solutions of polynomial growth has finite
dimension and the solutions are polynomials in time. Colding
and
Minicozzi \cite{CM:1} then obtained a sharp dimension bound of
this space. See also  the papers \cite{Ca:1}
and \cite{CM:2} for applications to the study of mean curvature
flows, and  \cite{Ha:1} in the graph case.
In a recent paper \cite{Z:1}, it was observed that ancient
solutions on the above ${\bf M}$ with exponential growth in the
space
variable are analytic in time. One application of this result
is
a necessary and sufficient condition on the solvability of the
backward heat equation in this class of solutions, which is
well
known to be ill-posed in general.
Backward heat equations have been studied by many
authors, see, for example, \cite{Mi:1} and \cite{Yo:1}; and
treated in many books. See, for instance, \cite{LL:1}.  They have been applied in such diverse fields as control theory, stochastic analysis,
Ricci flows etc.
There does not appear to be a necessary and sufficient
solvability criteria, except when
${\bf M}$ is a bounded domain for which semigroup theory gives an
abstract criteria. See \cite[Theorem 9]{CJ:1}.

One goal of the current paper is to show that the result in
\cite{Z:1} can be extended to solutions with  exponential
growth  of order $2$ (see \ref{expg}), which is a sharp condition.  Another  goal
is to prove the time analyticity for
all bounded mild solutions of the
Navier-Stokes equations in the whole space. One
implication is that bounded mild
solutions of the Navier-Stokes equations are analytic in
space-time, which yields the unique continuation
property of such solutions. This result may also
have applications in the study of
possible singularity whose blow up limit can be such a
solution.
We note that the space analyticity in more general
setting has been
proven in \cite{Ka:1, GK:1, GS:1, MS, GPS, DL, BBT, Gu, CKV:1, Xu:1},
to name a few.

In a subsequent work, we will study the corresponding problems in the half space.

We will present and prove the results for the heat equation and
the Navier-Stokes equations in Sections 2 and 3 respectively.

\section{The heat equation}

Let ${\bf M}$ be a $d$ dimensional, complete, noncompact Riemannian
manifold, $Ric$ be the Ricci curvature and $0$ be a reference
point on ${\bf M}$, $d(x, y)$ be the geodesic distance of $x, y \in
{\bf M}$. We will use $B(x, r)$  to denote the geodesic ball of
radius $r$ centered at $x$ and
$|B(x, r)|$ to denote the volume.  Given a point $(t,x)$ as
vertex, the standard parabolic cylinder of size $r$ is
$$
Q_r(t,x)=\{ (s,y)  \, | \, d(x, y)<r,  s \in [t-r^2, t] \}.
$$

\begin{theorem}
\label{thhepoly}
 Let ${\bf M}$ be a complete, $d$ dimensional, noncompact Riemannian
 manifold such that the Ricci curvature satisfies $Ric \ge
 -(d-1) K_0$ for a nonnegative constant $K_0$.

Let $u$ be a smooth solution of the heat equation $\partial_t
u-\Delta u=0$ on $[-2, 0] \times {{\bf M}}$ of   exponential growth of order $2$, namely
\begin{equation}
\label{expg}
 |u{(t,x)}| \le A_1 e^{ A_2  d^2(x, 0)}, \quad \forall (t,x)
 \in
 [-2, 0] \times {{\bf M}},
\end{equation} where $A_1$ and $A_2$ are positive constants.
Then $u=u(t,x)$ is analytic in $t \in [-1, 0]$ with radius
$r>0$  depending only on $d$, $K_0$, and $A_2$. Moreover, we
have
$$
u(t,x)= \sum^\infty_{j=0} a_j(x) \frac{ t^j}{j !}
$$
with $\Delta a_{j}(x) = a_{j+1}(x)$, and
$$
|a_{j}(x)| \le
A_1 \, A^{j+1}_3 j^j e^{2 A_2  d^2(x, 0)}, \quad
j=0,1,2,\ldots,
$$
where  $A_3$ is a positive constants depending only on $d$,
$K_0$, and $A_2$.
\end{theorem}

\begin{proof}
Since the equation is linear, without loss of generality, we
may
assume that $A_1=1$.
It suffices to prove the result for the space time point
$(0,x)$.
Let us recall a well-known parabolic mean value inequality
which
can be found, for instance, in \cite[Theorem 14.7]{Li:1}.
Suppose $v$ is a positive subsolution to the heat equation on
$[0, T] \times {{\bf M}}$ and $0$ is a point on ${\bf M}$. Let $T_1, T_2
\in [0, T]$ with $T_1<T_2$, $R>0$, $p>0$, and $\delta, \eta \in
(0, 1)$. Then there exist  positive constants $C_1$ and $C_2$,
depending only on $p$ and $d$, such that
$$
\aligned
&\sup_{[T_1, T_2]\times B(0, (1-\delta) R) }  v^p\\
&\le C_1
\frac{\bar{V}(2R)}{|B(0, R)|}
( R \sqrt{K_0} + 1) \exp ( C_2 \sqrt{K_0 (T_2-T_1)}) \\
&\qquad \times
\left(\frac{1}{\delta R} + \frac{1}{\sqrt{\eta T_1}} \right)^{d+2} \,
\int^{T_2}_{(1-\eta) T_1} \int_{B(0, R)} v^p(t,x)\ dx dt.
\endaligned
$$
Here $\overline{V}(R)$ is the volume of geodesic balls of radius $R$
in the simply connected space form with constant sectional
curvature $-K_0$.

Let $u$ be the given solution to the heat equation, so that
$u^2$ is a subsolution. Given $x_0 \in {\bf M}$ and a
positive integer $k$, with a translation of time, the  above
mean value inequality with $T_1=-1/k$, $T_2=0$, $R=1/\sqrt k$,
$\eta=\delta=1/2$ implies that
$$
\aligned
\sup_{Q_{1/(2 \sqrt{k})} (0,x_0)} u^2 &\le \frac{C_1
k^{d+2}}{|B(x_0, 1/\sqrt{k})|}
\int_{Q_{1/\sqrt{k}} (0,x_0)} u^2(t,x) \ dx dt\\
&\le \frac{C_2 k^{3d/2+2}}{|B(x_0, 1)|}
\int_{Q_{1/\sqrt{k}} (0,x_0)} u^2(t,x) \ dx dt,
\endaligned
$$
where we have used the Bishop-Gromov volume comparison
theorem. Note that the above mean value inequality is a local
one since the size of the cubes is less than one. Hence the
constants $C_1$ and $C_2$ are independent of $k$. Since
$\partial^k_t u$ is also a solution to the heat equation, it
follows that
\begin{equation}
\label{mviqdkt}
\sup_{Q_{1/(2 \sqrt{k})} (0,x_0)} (\partial^k_t u)^2
\le \frac{C_2 k^{3d/2+2}}{|B(x_0, 1)|}
\int_{Q_{1/\sqrt{k}} (0,x_0)} (\partial^k_t u)^2(t,x) \ dx dt.
\end{equation} Next we will bound the right-hand side.

For integers $j=1, 2, \ldots, k,$ consider the domains:
$$
\aligned
\Omega^1_{j}&=\{(t,x) \, | \, d(x, x_0)<j/\sqrt{k}, \,\,  t
\in
[-j/k, 0] \},\\
\Omega^2_j&=\{(t,x) \, | \, d(x, x_0)<(j+0.5)/\sqrt{k}, \,\,
t
\in [-(j+0.5)/k, 0] \}.
\endaligned
$$
Then it is clear that $\Omega^1_j \subset \Omega^2_j \subset
\Omega^1_{j+1}$.

Denote by $\psi^{(1)}_j$ a standard Lipschitz cutoff function
supported in
$$
\{(t,x) \, | \, d(x, x_0)<(j+0.5)/\sqrt{k}, \,\,  t \in (-(j+0.5)/k, (j+0.5)/k)
\}
$$
such that $\psi^{(1)}_j=1$ in $\Omega^1_j$ and $|\nabla
\psi^{(1)}_j|^2 + |\partial_t \psi^{(1)}_j| \le C k$.

 Since $u$ is a smooth solution to the heat equation, we
 deduce,
 by writing
  $\psi=\psi^{(1)}_j$, that
\[
\aligned
\int_{\Omega^2_j} &(u_t)^2 \psi^2 \ dx dt = \int_{\Omega^2_j}
u_t \Delta u \psi^2 \ dx dt\\
&=-\int_{\Omega^2_j} ((\nabla u)_t \nabla u) \, \psi^2 \ dx dt
- \int_{\Omega^2_j} u_t \nabla u \nabla \psi^2 \ dx dt\\
&= - \frac{1}{2} \int_{\Omega^2_j} (|\nabla u |^2)_t \, \psi^2
\
dx dt - 2 \int_{\Omega^2_j} u_t \psi \nabla u \nabla \psi \ dx
dt\\
&\le \frac{1}{2} \int_{\Omega^2_j} |\nabla u |^2 \, (\psi^2)_t
\
dx dt +\frac{1}{2}
 \int_{\Omega^2_j} (u_t)^2 \psi^2 \ dx dt + 2 \int_{\Omega^2_j}
 |\nabla u|^2 |\nabla \psi|^2 \ dx dt.
\endaligned
\]
Therefore,
\begin{equation}
\label{omg1j<}
\int_{\Omega^1_j} ( u_t)^2 \psi^2 \ dx dt \le C k
\int_{\Omega^2_j} |\nabla u |^2 \ dx dt.
\end{equation}

Denote by $\psi^{(2)}_j$ a standard Lipschitz cutoff function
supported in
$$
\{(t,x) \, | \, d(x, x_0)<(j+1)/\sqrt{k}, \quad  t \in
(-(j+1)/k, (j+1)/k) \}
$$
 such that $\psi^{(2)}_j=1$ in $\Omega^2_j$ and
$$
|\nabla
 \psi^{(2)}_j|^2 + |\partial_t \psi^{(2)}_j| \le C k.
$$
Using $(\psi^{(2)}_j)^2 u$ as a test function in the heat
equation, the standard Caccioppoli inequality (energy
estimate)
between the cubes $\Omega^2_j$ and  $\Omega^1_{j+1}$ shows
that
 \begin{equation}
\label{omg2j<}
\int_{\Omega^2_j} | \nabla u|^2 \ dx dt \le C k
\int_{\Omega^1_{j+1}}  u^2 \ dx dt.
\end{equation}  A combination of (\ref{omg1j<}) and (\ref{omg2j<}) gives
us
\begin{equation}
\label{ddu2r-4}
\int_{\Omega^1_j} ( u_t)^2  \ dx dt \le C_0 k^2
\int_{\Omega^1_{j+1}} u^2  \ dx dt,
\end{equation} where $C_0$ is a universal constant.

Since $\partial^j_t u$ is a solution, we can replace $u$ in
(\ref{ddu2r-4}) with $\partial^j_t u$ to deduce, after induction:
\begin{equation}
\label{utk<}
\int_{\Omega^1_1} (\partial^k_t u)^2  dx dt \le C^k_0 (k)^{2 k}
\int_{\Omega^1_k} u^2  \ dx dt.
\end{equation}

Note that $\Omega^1_1= Q_{1/\sqrt{k}}(0,x_0)$ and
$\Omega^1_k=[-1, 0] \times B(x_0, \sqrt{k})$. Substituting
(\ref{utk<}) into (\ref{mviqdkt}), we
find that
\[
 (\partial^k_t u)^2(0,x_0) \le \frac{C_2 k^{3d/2+2}}{|B(x_0,
 1)|} C^k_0 (k)^{2 k} \int_{[-1, 0] \times  B(x_0, \sqrt{k}) }
 u^2  \ dx dt.
\]
This implies, by the  growth condition
(\ref{expg}) and the Bishop-Gromov volume comparison theorem,
that
\begin{equation}
\label{djtu}
|\partial^k_t u(0,x_0)| \le  A^{k+1}_3 k^k e^{ 2 A_2 d^2(x_0,
0)}
\end{equation} for all integers $k \ge 1$. Here $A_3$ is a positive
constant depending only on $A_2$, $K_0$, and $d$ .
We remark that the volume of the ball in the denominator is
cancelled since
\[
|B(x_0, \sqrt{k})| \le e^{c \sqrt{k}} |B(x_0, 1)|.
\]

Fixing a number $R \ge 1$, for $x \in B(0, R)$, choose a
positive integer $j$  and $t \in [- \delta, 0]$
for some small $\delta>0$. Taylor's theorem implies that
\begin{equation}
\label{jtaylor}
u(t,x)- \sum^{j-1}_{i=0} \partial^i_t u(0,x) \frac{ t^i}{i !} =
\frac{t^j}{ j !} \partial^j_s u(s,x),
\end{equation} where $s=s(x, t, j) \in [t, 0]$.
By (\ref{djtu}), for sufficiently small $\delta>0$, the
right-hand side of (\ref{jtaylor}) converges to $0$ uniformly
for $x \in B(0, R)$
as $j \to \infty$. Hence
$$
u(t,x)= \sum^{\infty}_{j=0} \partial^j_t u(0,x) \frac{ t^j}{j
!},
$$
i.e., $u$ is analytic in $t$ with radius $\delta$.  Writing
$a_j= a_j(x) = \partial^j_t u(0,x)$. By (\ref{djtu}) again, we
have
$$
\partial_t u(t,x) = \sum^{\infty}_{j=0} a_{j+1}(x) \frac{
t^j}{j
!}
\quad \text{and}\quad
\Delta u(t,x) = \sum^{\infty}_{j=0} \Delta a_j(x) \frac{ t^j}{j
!},
$$
where both series converge uniformly for $(t,x) \in
[-\delta, 0] \times B(0, R) $ for any fixed $R>0$.
Since $u$ is a solution of the heat equation,
this implies
\[
\Delta a_j(x) =a_{j+1}(x)
\] with
\[
|a_j(x)| \le A^{j+1}_3 j^j e^{2 A_2 d^2(x, 0)}.
\] Here $A_3$ a positive constant depending only on $A_2$,
$K_0$, and $d$. This completes the proof of the theorem.
\end{proof}

An immediate application is the following:

\begin{corollary}
\label{cobhe}
Let ${\bf M}$ be as in the theorem. Then the Cauchy problem for the
backward heat equation
\begin{equation}
\label{bhe}
\begin{cases} \partial_t u+\Delta u  = 0,\\
u(0,x)=a(x)
\end{cases}
\end{equation} has a smooth  solution of  exponential growth  of order $2$ in
$(0,\delta) \times {{\bf M}}$ for some $\delta>0$ if and only if
\begin{equation}
\label{aijie}
|\Delta^j a(x)| \le A^{j+1}_3 j^j e^{ A_4  d^2(x, 0)}, \quad
j=0, 1,2,\ldots,
\end{equation} where  $A_3$ and $A_4$ are some positive constants.
\end{corollary}

\begin{proof}
Suppose (\ref{bhe}) has a smooth solution of  exponential
growth  of order $2$, say $u=u(t,x)$. Then
$u(x, -t)$ is a solution of the heat equation with  exponential
growth  of order $2$. By the theorem
\[
u(x, -t) = \sum^\infty_{j=0} a_j(x) \frac{(-t)^j}{j!}.
\] Then (\ref{aijie}) follows from the theorem since $\Delta^j
a(x) = a_j(x)$ in the theorem.

On the other hand, suppose (\ref{aijie}) holds. Then it is easy
to check that
\[
u(t,x) = \sum^\infty_{j=0} \Delta^j a(x) \frac{t^j}{j!}
\]is a smooth solution of the heat equation for $t \in
[-\delta,
0]$ with
$\delta$ sufficiently small. Indeed, the bounds (\ref{aijie})
guarantee that the above series and the series
\[
 \sum^\infty_{j=0} \Delta^{j+1} a(x) \frac{t^j}{j!} \quad\text{and}\quad
\sum^\infty_{j=0} \Delta^{j} a(x)  \frac{\partial_t t^j}{j!}
\]
all converge absolutely and uniformly in $[-\delta, 0]\times
B(0, R) $ for any fixed $R>0$. Hence $\partial_t u-\Delta u
=0$.
 Moreover $u$ has exponential
growth  of order $2$ since
 \[
|u(t,x)| \le \sum^\infty_{j=0} |\Delta^j a(x)| \frac{|t|^j}{j!}
\le A_3  e^{A_4 d^2(x, 0)} \sum^\infty_{j=0} \frac{\left(A_3  j
|t| \right)^j}{j!} \le A_3  e^{A_4 d^2(x, 0)}
\]
provided that $t \in [-\delta, 0]$ with $\delta$ sufficiently
small.
Thus $u(x, -t)$ is a solution to the Cauchy problem of the
backward heat equation (\ref{bhe}) of exponential
growth  of order $2$.
\end{proof}

{\remark  For the conclusion of the theorem to hold, some
growth
condition for the solution is necessary. Tychonov's
non-uniqueness example can be modified as follows. Let
$v=v(t,x)$ be Tychonov's solution of the heat equation in
$(-\infty, \infty)\times  {\mathbb R^d} $,  which is $0$ when $t \le
0$
but nontrivial for $t>0$.
Then $u \equiv v(x, t+1)$ is a nontrivial ancient solution. It
is clearly not analytic in time.
Note that $|u(t,x)|$ grows faster than $e^{c |x|^2}$  for any
$c>0$, but for any $\varepsilon>0$, $|u(x,t)|$ is bounded by
$Ce^{c|x|^{2+\varepsilon}}$ for some positive constants $c$ and
$C$. This implies that our growth condition is sharp}.

{\remark  If ${\bf M} =\mathbb R^d$,  it is well known that the
solution in the theorem is
also analytic in space variables. In fact, in this
case for the time analyticity the Laplace operator can be
replaced with a uniformly elliptic operator in divergence form
$D_i(a_{ij}D_j)$, where $a_{ij}$ are measurable functions
depending only on $x$. For general manifolds, the
space
analyticity requires certain bounds on curvature and its
derivatives.}

{\remark The time analyticity and backward solvability  results are still valid if the manifold ${\bf M}$ is replaced with
a bounded Lipschitz domain $D$ and the solutions are required to satisfy the Dirichlet or Neumann boundary condition. To justify, we can modify the proof of the theorem by replacing the geodesic balls with the fixed domain $D$ intersected with balls. The proof goes through for the following reasons. The first is that the mean value inequality with the geodesic balls replaced with $D$ intersected with balls still holds for $\partial^j_t u$ which satisfies the same boundary condition as $u$ itself. The second is that the boundary terms in the integration by parts procedure all vanish when the geodesic balls are replaced with $D$ intersected with balls.

All these results are also true with the appearance of a time independent inhomogeneous term, which is smooth and has at most exponential growth of order $2$, on the right-hand side of the heat equation. This may have applications in control theory.}

Next we present a further application of the main result in the section:  time analyticity of solutions of the heat equation down to the initial time $0$. Recall the following classical example from \cite{Kow:1}. Given the initial value $u_0(x) = 1/(1+ x^2)$ in $\mathbb R$, the solution to the Cauchy problem of the heat equation in $[0, \infty)\times \mathbb R $ is not analytic in time at $t=0$.
In the same paper, analyticity of solution down to $t=0$ is linked to the extension property of the initial value to an entire function in the complex plane with certain growth condition. See also \cite{Wi:1} Corollary 3.1b for a relatively modern approach. We mention that under the growth condition, time analyticity down to time $0$ also implies solvability of the backward heat equation, at least in short time. However it seems that the classical authors were mainly concerned with the concept of  analytic extension in space time without realizing that under the growth condition, solutions of the backward heat equation are analytic in time automatically.
The following result, which is an immediate consequence of the above corollary, provides a necessary and sufficient condition for solutions
to be analytic up to time $0$ without dependence on spatial analyticity, which is not available in the general setting.

\begin{corollary}
\label{cojiexi0}
Let ${\bf M}$ be as in the theorem. Then the Cauchy problem for the heat equation
\begin{equation}
\label{he2}
\begin{cases} \partial_t u -\Delta u  = 0,\\
u(0,x)=a(x)
\end{cases}
\end{equation} has a smooth  solution of exponential growth of order $2$, which is also analytic in time in
$[0, \delta) \times {{\bf M}}$ for some $\delta>0$ with a radius of convergence independent of $x$ if and only if
\begin{equation}
\label{aijie2}
|\Delta^j a(x)| \le A^{j+1}_3 j^j e^{ A_4  d^2(x, 0)}, \quad
j=0, 1,2,\ldots,
\end{equation} where  $A_3$ and $A_4$ are some positive constants.
\end{corollary}

\proof In the proof, all solutions are of exponential growth of order $2$.

Assuming (\ref{aijie2}),  it is a standard result that
 problem (\ref{he2}) has a solution $u=u(t, x)$ for some $\delta>0$. By Corollary \ref{cobhe}, the following backward problem also has a solution
\begin{equation}
\label{bhev}
\begin{cases} \partial_t v +\Delta v  = 0,\\
v(0,x)=a(x)
\end{cases}
\end{equation} in $[0,
\delta) \times {{\bf M}}.$ Define the function $U=U(t, x)$ by
\begin{equation}
U(t, x)=\begin{cases}  u(t, x), \quad t \in [0, \delta),\\
v(-t, x), \quad t \in (-\delta, 0].
\end{cases}
\end{equation} It is straight forward to check that $U$ is a solution of the heat equation in $(-\delta, \delta) \times {\bf M}$. By the theorem, $U$ and hence $u$ is analytic at time $0$. We mention that the time interval in the theorem is normalized to $[-2, 0]$ which can be changed to any finite interval.

On the other hand, suppose $u$ is a solution of the problem (\ref{he2}), which is analytic in time at $t=0$ with a radius of convergence independent of $x$. Then, by definition,  $u$ has a power series expansion in a time interval $(-\delta, \delta)$, for some $\delta>0$. Hence (\ref{aijie2}) holds following the proof of Corollary \ref{cobhe}, the first half.
\qed

\section{The Navier-Stokes equations}

The main result of this section is the following theorem.

\begin{theorem}
\label{thm2.1}
Assume that $u$ is a mild solution to the incompressible
Navier-Stokes equations
$$
u_t-\Delta u+u\cdot \nabla u+\nabla p=0
$$
on $[0,1]\times \mathbb R^d$ and
\begin{equation}
                                \label{eq7.19}
|u|\le C_2 \quad \text{in}\ \ [0,1]\times \mathbb R^d.
\end{equation}
Then for any $n\ge 1$,
\begin{equation*}

\sup_{t\in (0,1]} t^n \|\partial_t^n
u(t,\cdot)\|_{L_\infty(\mathbb R^d)}
\le N^{n+1}n^{n}
\end{equation*}
for some sufficiently large constant $N\ge 1$. Consequently,
$u(t,x)$ is analytic in time for any $t\in (0,1]$.
\end{theorem}

 The proof of the theorem relies on taking time derivative of
 the integral representation of the solution involving the
 Stokes kernel. One difficulty to overcome is that the time
 derivative of the Stokes kernel is not locally integrable in
 space time, let alone higher order derivatives.
We will manipulate the kernel function algebraically to allow
differentiation. This method seems to be applicable to other
types of equations. We also mention that non-mild solutions of
the Navier-Stokes equations need not be analytic in time, as
given by Serrin's example $u = a(t) \nabla h(x)$ where $h$ is a
harmonic function and $a=a(t)$ is an arbitrary smooth function.

The following lemma will be used frequently.

\begin{lemma}
                                    \label{lem2.1}
For any $n\ge 1$, we have
$$
\sum_{j=1}^{n-1}\binom{n}{j}j^{j-2/3}(n-j)^{n-j-2/3}\le
Cn^{n-2/3},
$$
\end{lemma}
where $C>0$ is a constant independent of $n$.
\begin{proof}
By the Stirling formula,
\begin{align*}
&\sum_{j=1}^{n-1}\binom{n}{j}j^{j-2/3}(n-j)^{n-j-2/3}
\le Cn^{n-2/3} \sum_{j=1}^{n-1} \frac
{n^{7/6}}{j^{7/6}(n-j)^{7/6}}\\
&=Cn^{n-2/3} \sum_{j=1}^{n-1} \left(\frac 1 j+\frac 1 {n-j}
\right)^{7/6}\\
&\le Cn^{n-2/3} \sum_{j=1}^{n-1}\left( \frac 1 {j^{7/6}}+\frac 1
{(n-j)^{7/6}} \right)
\le Cn^{n-2/3}.
\end{align*}
The lemma is proved.
\end{proof}

The next combinatorial lemma can be proved by using induction.

\begin{lemma}
                                \label{lem2.2}
Let $f$ and $g$ be two smooth functions on $\mathbb R$. For any
integer $n\ge 1$, we have
\begin{align*}
D^n(t^n f(t)g(t))&=\sum_{j=0}^n \binom{n}{j} D^j(t^j
f(t))D^{n-j}(t^{n-j}g(t))\\
&\quad -n\sum_{j=0}^{n-1} \binom{n-1}{j} D^j(t^j
f(t))D^{n-1-j}(t^{n-1-j}g(t)),
\end{align*}
where we denote $D=\partial_t$.
\end{lemma}
\begin{proof}
It follows from a straightforward computation by using
$$
D^n(t^n f(t)g(t))=tD^n(t^{n-1} f(t)g(t))+nD^{n-1}(t^{n-1}
f(t)g(t))
$$
and the inductive assumption.
\end{proof}

Let $\mathcal P$ be the Helmholtz (Leray--Hopf) projection in
$\mathbb R^d$, and
$E(t,x)=\mathcal P\Gamma(t,x)$ be the Stokes-Oseen kernel,
where
$$
\Gamma=(4\pi t)^{-d/2}e^{-|x|^2/(4t)}
$$
is
the heat kernel. Recall that $E$ satisfies the
homogeneous heat equation, the semigroup property, and
$$
E(t,x)=t^{-d/2}E(1,x/\sqrt t),
$$
where $E(1,\cdot)$ is a smooth function on $\mathbb R^d$ and decays
like $C/|x|^d$ as $x\to \infty$. Moreover,
$(\partial_t E)(1,x)$ and $(\nabla E)(1,x)$ decay like
$C/|x|^{d+2}$ and $C/|x|^{d+1}$ respectively as $x\to \infty$.
See, for instance, \cite{So}. Using these properties, we easily
obtain
\begin{equation}
                                \label{eq1.56a}
\|\nabla E(t,\cdot)\|_{L_1}\le C_0 t^{-1/2},
\end{equation}
and
\begin{equation*}
\|\partial_t^k E(t,\cdot)\|_{L_1}\le C_0^{k+1}k^{k-2/3}
t^{-k},\quad
\|\partial_t^k \nabla E(t,\cdot)\|_{L_1}\le C_0^{k+1}k^{k-2/3}
t^{-k-1/2}
\end{equation*}
for any integer $k\ge 1$ and $t>0$, where $C_0\ge 1$ is a
constant. It then follows from the Leibniz rule that
\begin{equation}
                                \label{eq1.56b}
\|\partial_t^k (t^k \nabla E(t,\cdot))\|_{L_1}\le
C_1^{k+1}k^{k-2/3} t^{-1/2}.
\end{equation}
Similarly, we have
\begin{equation}
                                \label{eq1.56c}
\|\partial_t^k (t^k \Gamma(t,\cdot))\|_{L_1}\le
C_1^{k+1}k^{k-2/3}.
\end{equation}

To prove Theorem \ref{thm2.1}, we first establish the following
proposition.
\begin{proposition}
                                    \label{prop2.2}
Under the conditions of Theorem \ref{thm2.1}, for any $n\ge 1$,
we have
\begin{equation}
                                    \label{eq2.48}
\sup_{t\in (0,1]} \|\partial_t^n (t^n
u(t,\cdot))\|_{L_\infty(\mathbb R^d)}
\le N^{n-1/2}n^{n-2/3}
\end{equation}
for some sufficiently large constant $N\ge 1$ depending only on the dimension and $\| u \|_{L_\infty}$.
\end{proposition}
\begin{proof}
We shall prove the proposition inductively.
As $u$ is a mild solution, we have
$$
u(t,x)=E(t,x)*u(0,x)-\int_0^t E(t-s,x)*\nabla (u\otimes
u)(s,x)\,ds,
$$
where $*$ denotes the spatial convolution. Then, by using
integration by parts,
\begin{align*}
&\partial_t^n (t^n u(t,x))\\
&=\partial_t^n (t^n
E(t,x)*u(0,x))-\partial_t^n \left(\int_0^{t} t^n \nabla
E(t-s,x)*(u\otimes u)(s,x)\,ds\right)\\
&:=I_1+I_2.
\end{align*}
By using \eqref{eq7.19} and \eqref{eq1.56c},
\begin{equation*}
|I_1|\le C_2C_1^{n+1}n^{n-2/3}\le N^{n-2/3}n^{n-2/3}
\end{equation*}
for sufficiently large $N$.

To estimate $I_2$, we first note that
\begin{align*}
&\int_0^{t} t^n \nabla E(t-s,x)*(u\otimes u)(s,x)\,ds\\
&=\sum_{k=0}^n \binom{n}{k} \int_0^{t} (t-s)^{k} \nabla
E(t-s,x)*\left(s^{n-k}(u\otimes u)(s,x)\right)\,ds.
\end{align*}
Therefore,
\begin{align*}
I_2&=-\sum_{k=0}^n \binom{n}{k} \partial_t^{n} \int_0^{t}
\big((t-s)^{k} \nabla E(t-s,x)\big)*\left(s^{n-k}(u\otimes
u)(s,x)\right)\,ds\\
&=-\sum_{k=0}^n \binom{n}{k} \partial_t^{n-k} \int_0^{t}
\partial_t^k\big((t-s)^{k} \nabla
E(t-s,x)\big)*\left(s^{n-k}(u\otimes u)(s,x)\right)\,ds\\
&=-\sum_{k=0}^n \binom{n}{k} \partial_t^{n-k} \int_0^{t}
\partial_s^k\big(s^{k} \nabla
E(s,x)\big)*\left((t-s)^{n-k}(u\otimes u)(t-s,x)\right)\,ds\\
&=-\sum_{k=0}^n \binom{n}{k} \int_0^{t} \partial_s^k\big(s^{k}
\nabla E(s,x)\big)*\partial_t^{n-k} \left((t-s)^{n-k}(u\otimes
u)(t-s,x)\right)\,ds,
\end{align*}
where in the third equality, we made a change of time variable $s \to t-s$, which allows us to
pass the time derivatives $\partial^{n-k}_t$ through the integral  without producing additional terms.

When $n=1$, we compute
\[
\begin{aligned}
\big|\partial_t &( t (u \otimes u)(t,x) ) \big| \\
&= \big|\partial_t  (t u) \otimes u (t, x) + u \otimes \partial_t (t u) (t, x) - u \otimes u (t, x) \big|
\\
& \le C \| u \|_{L_\infty} \big| \partial_t (t u)(t, x) \big| +
C   \| u \|^2_{L_\infty},
\end{aligned}
\] where $C>0$ depends only on the dimension $d$.
In general, by the inductive assumption and Lemmas \ref{lem2.2} and
\ref{lem2.1}, we have for $k=1,\ldots,n-1$,
\begin{equation}
                                \label{eq7.29}
|\partial_t^k (t^k (u\otimes u)(t,x))|
\le N^{k-1/3}k^{k-2/3}
\end{equation}
and
\begin{equation}
                                    \label{eq8.00}
|\partial_t^n (t^n (u\otimes u)(t,x))|
\le 2C_2 |\partial_t^n (t^n u(t,x))|+N^{n-3/4}n^{n-2/3}
\end{equation}
provided that $N$ is sufficiently large, depending only on the dimension $d$ and
$\Vert u \Vert_{L_\infty}$.
It then follows from Lemma \ref{lem2.1}, \eqref{eq1.56a},
\eqref{eq1.56b}, \eqref{eq8.00}, and \eqref{eq7.29} that
\begin{align*}
|I_2|&\le \int_0^t (t-s)^{-1/2}\Big[C_1^{n+1} n^{n-2/3}C_2^2
+C_0\big(2C_2\|\partial_t^n((t-s)^n
u(t-s,\cdot))\|_{L_\infty}\\
&\quad + N^{n-3/4}n^{n-2/3}\big)
+\sum_{k=1}^{n-1}\binom{n}{k}C_1^{k+1}k^{k-2/3} \cdot
N^{n-k-1/3}(n-k)^{n-k-2/3}\Big]\ ds\\
&\le N^{n-2/3}n^{n-2/3}t^{1/2}+2C_1C_2\int_0^t
s^{-1/2}\|\partial_s^n(s^n u(s,\cdot))\|_{L_\infty}
\ ds
\end{align*}
for sufficiently large $N$ depending on $C_1$ and $C_2$.

Combining the estimates of $I_1$ and $I_2$, we get
\eqref{eq2.48} by applying the Gronwall inequality, and
complete
the proof of the proposition.
\end{proof}

Finally, we complete the proof of Theorem \ref{thm2.1}.
\begin{proof}[Proof of Theorem \ref{thm2.1}]
Note that
$$
\partial_t^n(t^k u)=n\partial_t^{n-1}(t^{k-1}
u)+t\partial_t^n(t^{k-1}u).
$$
Taking $k=n$ and using \eqref{eq2.48}, we obtain
$$
\sup_{t\in (0,1]} \|t\partial_t^n (t^{n-1}
u(t,\cdot))\|_{L_\infty(\mathbb R^d)}
\le N^{n}(1+1/N)n^{n}.
$$
By induction,
$$
\sup_{t\in (0,1]} \|t^n\partial_t^n
u(t,\cdot)\|_{L_\infty(\mathbb R^d)}
\le N^{n}(1+1/N)^n n^{n}=(N+1)^n n^{n}.
$$
The theorem is proved.
\end{proof}

\section*{Acknowledgement} We wish to thank Prof. Bobo Hua,
Igor Kukavica, and F. H. Lin for helpful discussions.

\medskip

\noindent {\bf Funding:} Hongjie Dong was partially supported by the NSF under agreement DMS-1600593. Qi S. Zhang was partially supported by the Simons Foundation Grant No. 282153.