\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, let us formalize this and let $U = \{u_1 , ..., u_m\}$, be the users that previously have consumed items and let $F = \{S_1 , ..., S_n\}$ denote the items in the items selection. If we associate the users that have purchased item $S_i$ , we can view $S_i$ as a set of those users. The family $F$ represents the items, where $u_j$ is in $S_i$ if and only if user $u_j$ has consumed item $S_i$. Our objective now is to establish the $k$ sets $F^* = \{S_{i1}, ..., S_{ik}\}$ that together contain as many different users $u_j$ as possible. This is a well-known problem from Combinatorial Optimization denoted the Maximum k-Coverage problem and is formally defined as follows:\looseness=-1

\begin{problem}
  \problemtitle{\textsc{Maximum} $k$\textsc{-Coverage}}
  \probleminput{A universe of elements $U = \{u_1 , ..., u_m\}$, an integer value $k$ and a family of sets $F =
\{S_1, ..., S_n\}$, where each set $S_i$ is a subset of $U$.}
  \problemquestion{Find a subfamily $F^* \subseteq F$ such that $|F^*| \leq k$ and the number of covered elements
$|\bigcup_{S \in F^*} S|$ is maximised, i.e. using up to $k$ sets, cover as many elements as possible.}
\end{problem}

In general, we can say that the goal of Maximum Coverage is to find a subset of $F^*$ of items, such that $|F^*| \leq k$, that maximizes the number of different users reached. In other words, we want to find the $k$ movies that interested the most different users and recommend them to end users. Note that this problem is not interested in the consumption past of a specific user, but rather of all users of the data collection. 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
\vspace{-0.5cm}
\begin{figure}[ht]
	\begin{center}	
		\includegraphics[scale=0.55]{figures/fig::example.png}
		\caption{An illustrative example of the recommendation scenario, where Maximum k-Coverage can be applied.}
		\label{fig::CobMax}
	\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), so that the $S$ item that has not been previously selected ($S \in F \setminus F^*$) is selected and has the largest intersection with uncovered users ($|S \cap R|$), as shown in line 4. 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
