\newpage
\section{Exercise 1}
We can represent the problem using a Graph where the vertices represent a person, either male M or female F, and the edges represent friendship between two people. Each edge is denoted by a measure $w(x,y)$.
In order to satisfy the first constraint we use the densest subgraph problem whose purpose is to find a set of vertex that maximizes that maximizes the average degree.
For each iteration we pick a male $m$ and a female $f$ from the graph, so $|M|=|F|$.
\begin{algorithm}[H]
  \caption{Densest-Subgraph}\label{densest-subgraph}
  \begin{algorithmic}[1]
    \Procedure{Densest-Subgraph}{}
    \State $K_n \leftarrow G$
    \For{i = $|V|$ to 2}
    \State Let $M$ be the vertex of $K_i$ with minimum degree
    \State Let $F$ be the vertex of $K_i$ with minimum degree
    \State $K_{i-1}=K_i - \{m,f\}$
    \EndFor
    \State \textbf{return} $K_j$ \Comment{the subgraph among $K_i, i={1,...,|V|}$ with maximum density}
    \EndProcedure
  \end{algorithmic}
\end{algorithm}
\textbf{Theorem} \textit{The greedy algorithm Densest-Subgraph achieves a 2-approximation for the densest subgraph problem in undirected networks.}
\\
In an optimum solution, every vertex has degree $\geq \lambda$.
Let $S^*$ be the optimum solution, $e(S^*)$ the number of nodes and $|S^*|$ the number of nodes. We now define $\lambda^* = { e(S^*) \over {|S^*|}}$ as the optimal density.
Once the algorithm does the first steps, meaning once we remove M and F with the minumum degree, the optimal density is determinated by this inequality:
\begin{center}$ {e(S^*) \over |S^*|} \geq {e(S^*) - (\deg(m) + \deg(f)) \over |S^*|-2}$ (1)  \end{center}
Where $\deg(m)$ is the number of incident edges to M and $\deg(f)$ the number of incident edges to F.
\begin{center}$ \deg(m)+\deg(f) \geq {2 e (S^*) \over |S^*|} $ (2)\end{center}
Inequation (2) is valid $\forall (M, F)$
Now, knowing that $\sum_{v \in S^*} \deg(v) = 2 |E|$ applied to n $(M, F)$ couples $\sum_{m,f} \deg(m) + \deg(f) \leq 2 \lambda \cdot n $. But $2n = |S^*|$, so $\sum_{m,f} \deg(m) + \deg(f) \leq \lambda \cdot |S^*| $.
If the number of vertices in the subgraph is s, then the total number of edges is $\leq {\lambda s\over 2}$, and the density is $\leq \lambda/2$. Since the greedy algorithm returns the subgraph with the highest density over all the iterations, it always returns a subgraph with density at least $1 \over 2$ of the optimum.
\newpage