\section{Maximum User Coverage in Recommendation}

The proposed strategy aims to issue recommendations that suit the needs or interests of both mass and niche consumers. In this sense, we formalize the ramp-up problem as a variant of the Maximum $k$-Coverage problem as follows. Let $ U = \{u_1, u_2, ..., u_m\} $ be the set of $m$ distinct users existing in a system. Also, let $ I = \{i_1, i_2, ..., i_n \} $ be the set of $n$ distinct items available. Finally, let  $ F_n = \{S_1 , S_2, ..., S_k\} $ be a set of $n$ user subsets such that $S_l$ denotes the subset of users who have consumed the item $l$ in the system. The problem is to determine the subset $ F_{k}^{*} $ of size $k$ that maximizes the  number of distinct users who have consumed at least one of the items represented by the subsets of $ F_{k}^{*} $. Thus, we recommend to the first-time users the $k$ items consumed by the maximum number of distinct users in the system. The premise, in this case, is that this subset of items may suit the needs of a broad set of user profiles. \looseness=-1
 
Figure\ref{fig::CobMax}(a) depicts the movie context and can be replicated for various scenarios in the literature. In this context, users evaluate movies using a scale from 1 to 5. The value “0” indicates that the user does not evaluate the movie. Therefore, we can model the set of users and items presented in a system as a bipartite graph $G = (\{U,I\},E)$, where $U$ represents the users, $I$ the items and $E$ denotes the relationship between items and users (i.e., which user have consumed each item). The computational representation of this model can use any graph structure, such as adjacent matrix and incidence list. The result of this modeling is illustrated in Figure \ref{fig::CobMax}(b).\looseness=-1

\begin{figure}[ht]
	\begin{center}
		\label{fig::CobMax}

		\includegraphics[scale=0.55]{figures/fig::example.png}
		\caption{Ramp-up Problem Modeled as Graph for Maximum Coverage Strategy.}
	\end{center}
\end{figure}	

The Maximum Coverage problem is a variant of the well-studied problem of Vertex Cover \cite{alon2003online}. Unfortunately, these problems belong to the NP-complete class and it is unknown an  optimal solution to solve them in polynomial time. However, a simple greedy heuristic that, at each iteration, finds the item that maximizes the number of users approximates by 63\% the maximum number of users that can be covered, as demonstrated in \cite{chvatal1979greedy}. Algorithm \ref{alg01::greedy} presents this heuristic such as implemented for the recommendation task. This algorithm is implemented with time complexity $ O(kmn) $, where $ k $ is the number of recommended items, $ m $ the number of users and $ n $ the number of items.\looseness=-1

\begin{algorithm}
\caption{\textsc{Greedy-Max-Coverage($U$,$k$,$F$)}}
\label{alg01::greedy}
\begin{algorithmic}[1]
%\Procedure{CH\textendash Election}{}
\State $R \gets U$
\State $F^* \gets \emptyset$
\For{ $i$ from 1 to $k$ }
	\State $S \gets max_{S \in (F \setminus F^*)} |S \cap R|$
	\State $F^* \gets F^* \cup \{S\}$
	\State $R \gets R \setminus S$
	\If{$|R| = 0$}
		\State \textbf{break}
	\EndIf
\EndFor
\State \Return $F^*$
%\EndProcedure
\end{algorithmic}
\end{algorithm}

A preliminary assessment on the proposed strategy may lead us to assume the wrong conclusion that it simply retrieves the most popular items, since the goal is to find the items that coverage the largest number of users. However, observing the greedy algorithm presented in Algorithm \ref{alg01::greedy}, it is possible to realize that the chosen items are the ones that maximize the number of users at each iteration. In other words, the covered users are excluded from the set $R$, which corresponds to the analyzed users (line 6). Consequently, as the number of iterations approximates to $k$, the selected items become less popular. Despite not being consumed by many users, these items are the ones that maximize the coverage of users. In the example presented in Figure \ref{fig::CobMax}(b), the proposed algorithm first selects item $f_2$, which is the most popular one. Since users $u_2$, $u_4$, $u_7$ are covered by $f_2$, the algorithm removes them. At the next iteration, item $f_4$ is selected 
and users $u_1$, $u_3$, $u_5$ are removed. Finally, the algorithm selects item $f_3$, covering user $u_6$. Notice that $f_3$ is not popular, because only user $u_6$ has consumed it.\looseness=-1
