diff options
| -rw-r--r-- | greedy/main.tex | 561 | ||||
| -rw-r--r-- | greedy/sub.bib | 98 |
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} +} + |