Notes on greedy algorithms for submodular maximization

2 files changed, 659 insertions, 0 deletions

diff --git a/greedy/main.tex b/greedy/main.tex
new file mode 100644
index 0000000..def9d8e
--- /dev/null
+++ b/greedy/main.tex
@@ -0,0 +1,561 @@
+\documentclass[10pt, twocolumn]{article}
+\usepackage[hmargin=3em,vmargin=3em, bmargin=5em,footskip=3em]{geometry}
+\usepackage[sectionbib]{natbib}
+\usepackage[pagebackref=false,breaklinks=true,colorlinks=true,citecolor=blue]{hyperref}
+\usepackage[utf8x]{inputenc}
+\usepackage{times}
+\usepackage{amsmath,amsfonts,amsthm}
+\usepackage[english]{babel}
+\usepackage[capitalize, noabbrev]{cleveref}
+\usepackage{algorithm}
+\usepackage{algpseudocode}
+\usepackage{microtype}
+\setlength{\columnsep}{2em}
+
+\DeclareMathOperator*{\argmax}{arg\,max}
+\DeclareMathOperator{\E}{\mathbb{E}}
+\let\P\relax
+\DeclareMathOperator{\P}{\mathbb{P}}
+\newcommand{\ex}[1]{\E\left[#1\right]}
+\newcommand{\prob}[1]{\P\left[#1\right]}
+\newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
+\newcommand{\R}{\mathbf{R}}
+\newcommand{\N}{\mathbf{N}}
+\newcommand{\C}{\mathcal{C}}
+\newcommand{\eps}{\varepsilon}
+\newcommand{\cl}[1]{\text{\textbf{#1}}}
+\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
+
+\newtheorem{theorem}{Theorem}
+\newtheorem{proposition}[theorem]{Proposition}
+\newtheorem{lemma}[theorem]{Lemma}
+\newtheorem{corollary}[theorem]{Corollary}
+\theoremstyle{definition}
+\newtheorem{definition}[theorem]{Definition}
+\theoremstyle{remark}
+\newtheorem*{example}{Example}
+\newtheorem*{remark}{Remark}
+
+\algrenewcommand\algorithmicensure{\textbf{Output:}}
+\algrenewcommand\algorithmicrequire{\textbf{Input:}}
+
+\author{Thibaut Horel}
+\title{Notes on Greedy Algorithms for Submodular Maximization}
+
+\begin{document}
+\maketitle
+
+\section{Submodular Functions}
+
+All the functions we consider are set functions defined over subsets of
+a ground set $N$.
+
+\begin{definition}
+    A function $f:2^N\to\R$ is \emph{monotone} iff:
+    \begin{displaymath}
+        \forall S\subseteq T\subseteq N,\; f(S)\leq f(T)
+    \end{displaymath}
+\end{definition}
+
+\begin{definition}
+    For $f:2^N\to\R$ and $S\subseteq N$, the \emph{marginal
+    contribution} to $S$ is the function $f_S$ defined by:
+\begin{displaymath}
+    \forall T\subseteq N,\; f_S(T) = f(S\cup T) - f(S)
+\end{displaymath}
+\end{definition}
+
+When there is no ambiguity, we write $f_S(e)$ instead of $f_S(\{e\})$ for $e\in
+N$, $S+e$ instead of $S\cup\{e\}$ and $S-e$ instead of $S\setminus\{e\}$.
+
+\begin{definition}
+    \label{def:sub}
+    A function $f:2^N\to\R$ is \emph{submodular} iff:
+\begin{displaymath}
+    \forall S\subseteq T\subseteq N,\forall e\in N\setminus T,\;
+    f_T(e)\leq f_S(e)
+\end{displaymath}
+\end{definition}
+
+This ``decreasing marginal contribution'' definition of submodular functions
+often leads to treating them as ``discrete concave functions''.
+
+\begin{proposition}
+    \label{prop:subeq}
+    The following statements are equivalent:
+    \begin{enumerate}
+        \item $f$ is submodular.
+        \item for all $S\subseteq N$, $f_S$ is submodular.
+        \item for all $S\subseteq N$, $f_S$ is subadditive.
+    \end{enumerate}
+\end{proposition}
+
+\begin{proof}
+    (\emph{1. $\Rightarrow$ 2.}) is immediate. To prove (\emph{2. $\Rightarrow$
+    3.}), we show that any submodular function $f$ is subadditive. Let $f$ be
+      a submodular function. Consider $A$ and $B$ two subets of $N$. Writing $B
+      = \{e_1,\dots,e_n\}$ and $B_i = \{e_1,\ldots,e_i\}$:
+      \begin{align*}
+          f(A\cup B) &= f(A) + \sum_{i=1}^n f(A\cup B_i) - f(A\cup B_{i-1})\\
+                     &\leq f(A) + \sum_{i=1}^n f(B_i) - f(B_{i-1}) = f(A)
+          + f(B)
+        \end{align*}
+    where the inequality uses the submodularity of $f$.
+
+    Finally, we prove (\emph{3. $\Rightarrow$ 1.}). Let $f$ be a function
+    satisfying \emph{3.}, and let us consider $S\subseteq T\subseteq N$ and
+    $e\in N\setminus T$. Writing $T' = T\setminus S$:
+    \begin{align*}
+        f_T(e) &= f_S(T'+e) - f_S(T')\\
+                   &\leq f_S(T') + f_S(e) - f_S(T') = f_S(e)
+    \end{align*}
+    where the inequality used that $f_S$ is subadditive.
+\end{proof} 
+
+\begin{remark}
+    \cref{prop:subeq} implies in particular that a submodular function is
+    subadditive.
+\end{remark}
+
+The following \lcnamecref{cor:sa} will be very useful in analysing greedy
+algorithms involving submodular functions.  It can be seen as the
+``integrated'' version of \cref{def:sub}\footnote{Note the analogy with
+$f(b)\leq f(a) + (b-a)f'(a)$, for $f$ concave.}.
+
+\begin{corollary}
+    \label{cor:sa}
+Let $f$ be a submodular function, then:
+\begin{displaymath}
+    \forall S\subseteq T\subseteq N,\;
+    f(T)\leq f(S) + \sum_{e\in T\setminus S} f_S(e)
+\end{displaymath}
+Furthermore, if $f$ is monotone submodular, $S$ need not be a subset of $T$:
+\begin{displaymath}
+    \forall S\subseteq N,\, T\subseteq N,\;
+    f(T)\leq f(S) + \sum_{e\in T\setminus S} f_S(e)
+\end{displaymath}
+\end{corollary}
+
+\begin{proof}
+If $f$ is submodular, using that $f_S$ is subadditive:
+\begin{displaymath}
+    f_S(T) = f_S(T\setminus S)\leq \sum_{e\in T\setminus S} f_S(e)
+\end{displaymath}
+which proves the first part of the corollary.
+
+If $f$ is monotone submodular, $f(T)\leq f(S\cup T)$ and applying the first
+part of the corollary to $S\cup T$ and $T$ concludes the proof.
+\end{proof}
+
+\begin{remark}
+    The two inequalities of \cref{cor:sa} can be proved to be respectively
+    equivalent to ``$f$ is submodular'' and ``$f$ is monotone submodular''.
+\end{remark}
+
+\section{Cardinality Constraint}
+
+Henceforth, $f$ will be a monotone submodular function. Furthermore, we 
+assume that $f$ is \emph{normalized}, that is, $f(\emptyset) = 0$. Consider
+the following maximization program:
+\begin{displaymath}
+    S^*\in\argmax_{S\,:\, |S|\leq K} f(S)
+\end{displaymath}
+
+The choice of a representation for $f$ has a big impact on the computational
+nature of the above program. We assume the \emph{value query model}: for any
+$S\subseteq N$, the algorithm can query a black-box oracle for the value
+$f(S)$. An algorithm making $O\big(\text{poly}(|N|)\big)$ queries to the oracle
+is considered to have polynomial running time.
+
+\begin{algorithm}
+    \caption{Greedy (Cardinality constraint)}
+    \label{alg:gc}
+    \begin{algorithmic}[1]
+        \Require $N$, $K$, value query oracle for $f$
+        \State $S_G \gets \emptyset$
+        \While{$|S_G| < K$}
+        \State $x^*\gets \argmax_{x\in N} f_{S_G}(x)$
+        \State $S_G \gets S_G + x^*$\label{line:add1}
+            \State $N\gets N - x^*$
+        \EndWhile
+        \State\textbf{return} $S_G$
+    \end{algorithmic}
+\end{algorithm}
+
+\begin{proposition}
+    Let $S_G$ be the set returned by Algorithm~\ref{alg:gc}, then
+    $f(S_G)\geq\big(1-\frac{1}{e}\big) f(S^*)$.
+\end{proposition}
+
+\begin{proof}
+    Let us denote by $S_i = \{e_1,\dots, e_i\}$, the value of $S_G$ after the
+    $i$th time line~\ref{line:add1} of Algorithm~\ref{alg:gc} is executed.
+    Then:
+    \begin{align*}
+        f(S^*)&\leq f(S_{i-1})
+        + \sum_{e\in S^*\setminus S_{i-1}} f_{S_{i-1}}(e)\\
+        &\leq f(S_{i-1})
+        + \sum_{e\in S^*\setminus S_{i-1}} f(S_i) - f(S_{i-1})\\
+        &\leq f(S_{i-1}) + K\big(f(S_i) - f(S_{i-1})\big)
+    \end{align*}
+    where the first inequality used \cref{cor:sa}, the second inequality used
+    the greediness of Algorithm~\ref{alg:gc} and the third inequality used that
+    $|S^*|\leq K$.
+
+    Subtracting $K\cdot f(S^*)$ both sides gives:
+    \begin{displaymath}
+        f(S_i) - f(S^*)\geq \frac{K-1}{K} \big(f(S_{i-1}) - f(S^*)\big)
+    \end{displaymath}
+    which in turn implies by induction:
+    \begin{displaymath}
+        f(S_i)
+        \geq \left(1-\left(1-\frac{1}{K}\right)^i\right) f(S^*)
+    \end{displaymath}
+    Taking $i=K$ and using $(1-\frac{1}{K})^K\leq \frac{1}{e}$ concludes the
+    proof.
+\end{proof}
+
+\begin{remark}
+    \cite{feige1998} proved that unless $P=NP$, no polynomial time algorithm
+    can achieve an approximation ratio better than $1-\frac{1}{e}$ for the
+    cardinality constrained maximization of set cover functions.
+\end{remark}
+
+\section{Knapsack Constraint}
+
+There is now a cost function $c:N\to\R^+$ and a budget $B\in\R^+$. $c$ is
+extended to $2^N$ by $c(S) = \sum_{e\in S} c(e)$. Consider the following
+Knapsack constrained optimization problem:
+\begin{displaymath}
+    S^*\in\argmax_{S\,:\, c(S)\leq B} f(S)
+\end{displaymath}
+
+A natural way to extend Algorithm~\ref{alg:gc} to this case is
+Algorithm~\ref{alg:gk}. The two main differences are that:
+\begin{enumerate}
+    \item instead of maximizing the marginal contribution at each time step,
+        Algorithm~\ref{alg:gk} maximizes the ``bang-per-buck'': the marginal
+        contribution divided by the cost.
+    \item when adding an item would violate the budget constraint, the item is
+        thrown away, and the iteration keeps inspecting possibly cheaper items.
+\end{enumerate}
+
+Unfortunately, Algorithm~\ref{alg:gk} has unbounded approximation ratio.
+Similarly to the standard Knapsack problem (when $f$ is additive), problems
+arise when there are high value items. Consider the case where $f$ is additive
+and $N = \{e_1, e_2\}$ with $f(e_1) = v$, $f(e_2) = \eps v$, $c(e_1) = B$ and
+$c(e_2) = \frac{\eps B}{2}$. The best solution is clearly to pick $\{e_1\}$ for
+a value of $v$. In contrast, Algorithm~\ref{alg:gk} picks $\{e_2\}$ for a value
+of $\eps v$. As $\eps$ gets close to zero, the approximation ratio becomes
+arbitrarily large.
+
+\begin{algorithm}
+    \caption{Greedy (Knapsack constraint)}
+    \label{alg:gk}
+    \begin{algorithmic}[1]
+        \Require $N$, $B$, value query oracle $f$, cost function $c$
+        \State $S_G \gets \emptyset$
+        \While{$N\neq \emptyset$}
+        \State $x^*\gets \argmax_{x\in N} \frac{f_{S_G}(x)}{c(x)}$
+        \If{$c(S_G)+c(x^*)\leq B$}\label{line:budget}
+        \State $S_G \gets S_G + x^*$\label{line:add2}
+            \EndIf
+            \State $N\gets N - x^*$
+        \EndWhile
+        \State\textbf{return} $S_G$
+    \end{algorithmic}
+\end{algorithm}
+
+However, the following lemma will be useful to use Algorithm~\ref{alg:gk} as
+a building block for algorithms solving the Knapsack constrained submodular
+maximization.
+
+\begin{lemma}
+    \label{lemma:greedy}
+    Whenever line~\ref{line:budget} of Algorithm~\ref{alg:gk} evaluates to
+    False, $f(S_G+x^*)\geq \big(1-\frac{1}{e}\big) f(S^*)$.
+\end{lemma}
+
+\begin{proof} 
+    Let us denote by $S_i = \{e_1,\dots, e_i\}$, the value of $S_G$ after the
+    $i$th time line~\ref{line:add2} of Algorithm~\ref{alg:gk} is executed.
+    Then:
+    \begin{align*}
+        f(S^*)
+        &\leq f(S_{i-1}) + \sum_{e\in S^*\setminus S_{i-1}} f_{S_{i-1}}(e)\\
+        &= f(S_{i-1}) + \sum_{e\in S^*\setminus S_{i-1}}
+        c(e)\frac{f_{S_{i-1}}(e)}{c(e)}\\
+        &\leq f(S_{i-1}) + \frac{f(S_{i})-f(S_{i-1})}{c(e_i)}\sum_{e\in S^*\setminus S_{i-1}}
+        c(e)\\
+        &\leq f(S_{i-1}) + \frac{B}{c(e_i)}\big(f(S_{i})-f(S_{i-1})\big)
+    \end{align*}
+    where the first inequality used \cref{cor:sa}, the second inequality used
+    the greediness of Algorithm~\ref{alg:gk} and the last inequality used that
+    $c(S^*)\leq B$.
+
+    Subtracting $\frac{B}{c_i}$ both sides and reordering the terms:
+    \begin{displaymath}
+        f(S_i)- f(S^*)
+        \geq \left(1- \frac{c(e_i)}{B}\right)\big(f(S_{i-1}) - f(S^*)\big)
+    \end{displaymath}
+    Solving this recursive inequality yields:
+    \begin{displaymath}
+        f(S_i)
+        \geq \left(1-\prod_{k=1}^i\left(1- \frac{c(e_i)}{B}\right)\right) f(S^*)
+    \end{displaymath}
+    Finally, using that $1-x\leq e^{-x}$:
+    \begin{displaymath}
+        f(S_i)
+    \geq \left(1-\exp \frac{-c(S_i)}{B}\right) f(S^*)
+    \end{displaymath}
+
+    We are now ready to prove the lemma. Let us consider $S_G$ at some
+    iteration of Algorithm~\ref{alg:gk} where line~\ref{line:add2} evaluates to
+    false. The above analysis didn't assume that line~\ref{line:add2} evaluated
+    to True when element $e_i$ was added to $S_G$, hence we can apply it to
+    $S_G+x^*$:
+    \begin{displaymath}
+        f(S_G+x^*)
+    \geq \left(1-\exp \frac{-c(S_G)-c(x^*)}{B}\right) f(S^*)
+    \end{displaymath}
+    and using that $c(S_G) + c(x^*) > B$ by assumption of \cref{lemma:greedy}
+    concludes the proof.
+\end{proof}
+
+We now present two algorithms which exploit \cref{lemma:greedy} to obtain
+a constant approximation ratio to the optimal solution.
+
+\begin{algorithm}
+    \caption{Greedy (Knapsack constraint), simple fix}
+    \label{alg:gk1}
+    \begin{algorithmic}[1]
+        \Require $N$, $B$, value query oracle $f$, cost function $c$
+        \State $e^*\gets \argmax_{e\in N,\, c(e)\leq B} f(e)$
+        \State $S_G \gets$ result of Algorithm~\ref{alg:gk}
+        \State\textbf{return} $\argmax\{f(S_G),f(e^*)\}$
+    \end{algorithmic}
+\end{algorithm}
+
+\begin{proposition}
+    Let $S$ be the set returned by Algorithm~\ref{alg:gk1}, then $f(S)\geq
+    \frac{1}{2}\left(1-\frac{1}{e}\right) f(S^*)$.
+\end{proposition}
+
+\begin{proof}
+    Let us consider the value of $S_G$ the first time line~\ref{line:budget} of
+    Algorithm~\ref{alg:gk} evaluated to False after the last element of $S_G$
+    was added:
+    \begin{align*}
+        2 f(S)&\geq f(S_G) + f(e^*)\geq f(S_G) + f(x^*)\\
+              &\geq f(S_G+x^*) \geq \left(1-\frac{1}{e}\right)f(S^*)
+    \end{align*}
+    where the first inequality used the definition of $S$, the second
+    inequality used the definition of $e^*$, the third inequality used the
+    subadditivity of $f$ and the last inequality used Lemma~\ref{lemma:greedy}.
+\end{proof}
+
+\begin{remark}
+    \cite{lin2010} noted that the above analysis can be refined to show that
+    the approximation ratio of Algorithm~\ref{alg:gk1} is at least
+    $1-\frac{1}{\sqrt{e}}$.
+\end{remark}
+
+\begin{algorithm}
+    \caption{Greedy (Knapsack constraint), partial enumeration}
+    \label{alg:gk2}
+    \begin{algorithmic}[1]
+        \Require $N$, $B$, value query oracle $f$, cost function $c$
+        \State $S_1\gets \argmax_{S\subseteq N,\, c(S)\leq B,\, |S| < d} f(S)$
+        \State $S_2 \gets \emptyset$
+        \ForAll{$S\subseteq N,\, |S|=d, c(S)\leq B$}
+            \State $N'\gets N\setminus S$
+            \State $S_G \gets$ Algorithm~\ref{alg:gk} for $N'$ and
+            initialization $S_G\gets S$\label{line:greedy}
+            \If{$f(S_G) > f(S_2)$}
+                \State $S_2\gets S_G$
+            \EndIf
+        \EndFor
+        \State\textbf{return} $\argmax\{f(S_1),f(S_2)\}$
+    \end{algorithmic}
+\end{algorithm}
+
+For some constant $d$ (fixed later in the analysis), Algorithm~\ref{alg:gk2}
+first compute $S_1$, the set of maximum value among all sets of at most $d-1$
+elements. Then for all sets of $S$ of $d$ elements, the algorithm completes $S$
+greedily using Algorithm~\ref{alg:gk} where the initialisation
+$S_G\gets\emptyset$ is replaced by $S_G\gets S$. The best set obtained by such
+a greedy completion is $S_2$. Algorithm~\ref{alg:gk2} then returns the best of
+$S_1$ and $S_2$.
+
+\begin{proposition}
+    For $d=3$, let $S$ be the set returned by Algorithm~\ref{alg:gk2}, then
+    $f(S)\geq \left(1-\frac{1}{e}\right) f(S^*)$.
+\end{proposition}
+
+\begin{proof}\emph{Wlog}, assume that $|S^*| > d$, otherwise
+    Algorithm~\ref{alg:gk2} finds the optimal solution. Let us write $S^*
+    = \{e_1^*,\ldots e_n^*\}$ and $S^*_i = \{e_1^*,\dots,e_i^*\}$ where the
+    elements of $S^*$ where ordered such that:
+    \begin{displaymath}
+        e_i^* \in \argmax_{e\in S^*\setminus S^*_{i-1}} f_{S^*_{i-1}}(e)
+    \end{displaymath}
+
+    Let us now consider the iteration of Algorithm~\ref{alg:gk2} where
+    $S=S^*_d$. Then line~\ref{line:greedy} is equivalent to running
+    Algorithm~\ref{alg:gk} for the function $f_{S_d^*}$ and set $N\setminus
+    S^*_d$. Let us consider the first time line~\ref{line:add1} of
+    Algorithm~\ref{alg:gk} evaluated to false for some element $x^*$ of
+    $S^*\setminus S^*_d$\footnote{This necessarily happens since all the
+    elements in $N$ are eventually considered in the while loop.}. Then by
+    Lemma~\ref{lemma:greedy}:
+    \begin{equation}
+        \label{eq:foo1}
+        f(S_G + x^*) - f(S_d^*)\geq \left(1-\frac{1}{e}\right) \big(f(S^*)
+        - f(S^*_d)\big)
+    \end{equation}
+    But by submodularity of $f$ and the ordering of $S^*_d$:
+    \begin{displaymath}
+        f_{S_G}(x^*)\leq f_{S_i^*}(x^*)\leq f(S_i^*) -f(S_{i-1}^*),
+        \quad 1\leq i \leq d
+    \end{displaymath}
+    Summing for $1\leq i\leq d$:
+    \begin{equation}
+        \label{eq:foo2}
+        f(S_G+x^*)\leq f(S_G) + \frac{1}{d} f(S_d^*)
+    \end{equation}
+    Combining \cref{eq:foo1,eq:foo2} gives
+    \begin{displaymath}
+        f(S_G)\geq \left(1-\frac{1}{e}\right)f(S^*)
+        + \left(\frac{1}{e}-\frac{1}{d}\right) f(S^*_d)
+    \end{displaymath}
+    which concludes the proof after observing that $\frac{1}{e}-\frac{1}{d}>0$
+    for $d=3$.
+\end{proof}
+
+\section{Matroid Constraint}
+
+\begin{definition}
+    A \emph{matroid} $M$ is a pair $(N,\mathcal{I})$. $N$ is a finite set
+    called the \emph{ground set} and $\mathcal{I}$ is family of subsets of $N$
+    called the \emph{independent sets} such that:
+    \begin{enumerate}
+        \item (downward closure) if $B\in\mathcal{I}\text{ and } A\subseteq B$
+            then $A\in\mathcal{I}$
+        \item (exchange property) if $A\in\mathcal{I}, B\in\mathcal{I}$ and
+            $|A| < |B|$ then there exists $x\in B\setminus A$ such that
+            $A+x\in \mathcal{I}$
+    \end{enumerate}
+    Maximal independent sets of $M$ are called \emph{bases}.
+\end{definition}
+
+\begin{remark}
+It follows from the exchange property that all bases have the same cardinality.
+This cardinality is the \emph{rank} of $M$.
+\end{remark}
+
+\begin{proposition}[bijective basis exchange]
+    \label{prop:bbe}
+    If $B_1$ and $B_2$ are two bases of a matroid $M$, then there exists
+    a bijection $\phi:B_1\setminus B_2\to B_2\setminus B_1$ such that:
+    \begin{displaymath}
+        \forall x\in B_1\setminus B_2,\;
+        B_1 - x + \phi(x)\in\mathcal{I}
+    \end{displaymath}
+\end{proposition}
+
+\begin{proof} This is a standard result in matroid theory.
+\end{proof}
+
+\begin{remark}
+    The bijection $\phi$ of \cref{prop:bbe} can be extended to $\phi:B_1\to
+    B_2$ by defining it to be the identity function on $B_1\cap B_2$.
+\end{remark}
+
+We now look at the problem of maximizing a monotone submodular function over
+a matroid $M=(N,\mathcal{I})$:
+\begin{displaymath}
+    S^* \in \argmax_{S\in\mathcal{I}} f(S)
+\end{displaymath}
+From a computational perspective, we still assume a value query oracle for $f$.
+Furthermore, we assume an \emph{independence oracle} for $M$: given
+$S\subseteq N$, the independence oracle tests whether or not
+$S\in\mathcal{I}$.
+
+\begin{algorithm}
+    \caption{Greedy (Matroid constraint)}
+    \label{alg:gmat}
+    \begin{algorithmic}[1]
+        \Require{$N$, value query oracle $f$, independence oracle for
+        $\mathcal{I}$}
+        \State $S_G \gets \emptyset$
+        \While{$N\neq \emptyset$}
+        \State $x^*\gets \argmax_{x\in N} f_{S_G}(x)$
+            \If{$S_G+x\in\mathcal{I}$}
+            \State $S_G \gets S_G + x^*$
+            \EndIf
+            \State $N\gets N - x^*$
+        \EndWhile
+        \State\textbf{return} $S_G$
+    \end{algorithmic}
+\end{algorithm}
+
+\begin{remark}
+    The set $S_G$ constructed by Algorithm~\ref{alg:gmat} is a base of $M$.
+    When the rank $K$ of $M$ is known, the while loop can be stopped as soon as
+    $|S_G| = K$ (cf. cardinality constrained submodular maximization).
+\end{remark}
+
+\begin{proposition}
+    Let $S_G$ be the set returned by Algorithm~\ref{alg:gmat}, then $f(S_G)\geq
+    \frac{1}{2} f(S^*)$.
+\end{proposition}
+
+\begin{proof}
+    \emph{Wlog}, assume that $S^*$ is a base of $M$. Let $\phi:S^*\to
+    S_G$ be a bijection as in \cref{prop:bbe}. Le us write:
+    \begin{displaymath}
+        S^* = \{e_1^*,\ldots, e_K^*\}
+        \text{ and }
+        S_G = \{e_1,\ldots, e_K\}
+    \end{displaymath}
+    where $e_i =\phi(e_i^*)$ and define $S_i = \{e_1,\dots,e_i\}$. Then:
+    \begin{align*}
+        f(S^*) -  f(S_G) &\leq \sum_{i=1}^K f_{S_G}(e_i^*)
+        \leq\sum_{i=1}^K f_{S_{i-1}}(e_i^*)\\
+        %&\leq\sum_{i=1}^K f_{S_{i-1}}(e_i)
+        &\leq\sum_{i=1}^K f(S_i) - f(S_{i-1})
+              = f(S_G)
+    \end{align*}
+    where the first inequality used \cref{cor:sa}, the second inequality used
+    submodularity of $f$, and the third inequality used the greediness of
+    Algorithm~\ref{alg:gmat} and that $S_{i-1}+e_i^*\in\mathcal{I}$ by
+    \cref{prop:bbe}.
+\end{proof}
+
+\section{Bibliographical Notes}
+
+A systematic analysis of greedy algorithms for submodular maximization was made
+by \cite{fisher1978,nemhauser1978}. The results about submodular maximization
+under cardinality and matroid constraints can be found in these papers, even
+though some of them  had already been obtained by \cite{edmonds1971}. The lower
+bound of $(1-\frac{1}{e})$ for the approximation ratio of a polynomial time
+algorithm is due to \cite{feige1998}.
+
+For Knapsack constraints, \cite{Khuller1999} were the first to obtain an
+approximation ratio of $(1-\frac{1}{e})$ using partial enumeration in the case
+of a set cover function. It was then noted by \cite{sviridenko2004}, that the
+result extended to any submodular function.
+
+It is possible to obtain a $(1-\frac{1}{e})$ approximation ratio under matroid
+constaints. This result was first obtained by \cite{calinescu2007} using
+continuous optimization. A combinatorial algorithm was later constructed by
+\cite{filmus2012}.
+
+More complex constraints can also be considered: intersection of independence
+systems, matroids, knapsack constraints. \cite{nemhauser1978} summarize some
+results from the late 70's. A general framework can be found in
+\cite{vondrak2011}.
+
+\bibliographystyle{abbrvnat}
+\bibliography{sub}
+\end{document}
diff --git a/greedy/sub.bib b/greedy/sub.bib
new file mode 100644
index 0000000..5adbe9b
--- /dev/null
+++ b/greedy/sub.bib
@@ -0,0 +1,98 @@
+@book{fisher1978,
+  title={An analysis of approximations for maximizing submodular set functions—II},
+  author={Fisher, Marshall L and Nemhauser, George L and Wolsey, Laurence A},
+  year={1978},
+  publisher={Springer}
+}
+
+@article{nemhauser1978,
+  title={An analysis of approximations for maximizing submodular set functions—I},
+  author={Nemhauser, George L and Wolsey, Laurence A and Fisher, Marshall L},
+  journal={Mathematical Programming},
+  volume={14},
+  number={1},
+  pages={265--294},
+  year={1978},
+  publisher={Springer}
+}
+
+@article{edmonds1971,
+  title={Matroids and the greedy algorithm},
+  author={Edmonds, Jack},
+  journal={Mathematical programming},
+  volume={1},
+  number={1},
+  pages={127--136},
+  year={1971},
+  publisher={Springer}
+}
+
+@article{feige1998,
+  title={A threshold of ln n for approximating set cover},
+  author={Feige, Uriel},
+  journal={Journal of the ACM (JACM)},
+  volume={45},
+  number={4},
+  pages={634--652},
+  year={1998},
+  publisher={ACM}
+}
+
+@article{khuller1999,
+  title={The budgeted maximum coverage problem},
+  author={Khuller, Samir and Moss, Anna and Naor, Joseph Seffi},
+  journal={Information Processing Letters},
+  volume={70},
+  number={1},
+  pages={39--45},
+  year={1999},
+  publisher={Elsevier}
+}
+
+@article{sviridenko2004,
+  title={A note on maximizing a submodular set function subject to a knapsack constraint},
+  author={Sviridenko, Maxim},
+  journal={Operations Research Letters},
+  volume={32},
+  number={1},
+  pages={41--43},
+  year={2004},
+  publisher={Elsevier}
+}
+
+@incollection{calinescu2007,
+  title={Maximizing a submodular set function subject to a matroid constraint},
+  author={Calinescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan},
+  booktitle={Integer programming and combinatorial optimization},
+  pages={182--196},
+  year={2007},
+  publisher={Springer}
+}
+
+@inproceedings{filmus2012,
+  title={A tight combinatorial algorithm for submodular maximization subject to a matroid constraint},
+  author={Filmus, Yuval and Ward, Justin},
+  booktitle={Foundations of Computer Science (FOCS)},
+  pages={659--668},
+  year={2012},
+  organization={IEEE}
+}
+
+@inproceedings{vondrak2011,
+  title={Submodular function maximization via the multilinear relaxation and contention resolution schemes},
+  author={Vondr{\'a}k, Jan and Chekuri, Chandra and Zenklusen, Rico},
+  booktitle={Proceedings of the forty-third annual ACM symposium on Theory of computing},
+  pages={783--792},
+  year={2011},
+  organization={ACM}
+}
+
+@inproceedings{lin2010,
+  title={Multi-document summarization via budgeted maximization of submodular functions},
+  author={Lin, Hui and Bilmes, Jeff},
+  booktitle={Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics},
+  pages={912--920},
+  year={2010},
+  organization={Association for Computational Linguistics}
+}
+