path: root/greedy/main.tex

\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 to
$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 $\text{P}=\text{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{khuller1999} 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 to combine constraints can be
found in \cite{vondrak2011}.

\bibliographystyle{abbrvnat}
\bibliography{sub}
\end{document}