From d48aae30c2bc357b3125d9a9a6678f12427731b3 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sat, 21 Feb 2015 16:08:34 -0500
Subject: Proper attribution, minor fixes

---
 greedy/main.tex | 17 +++++++++--------
 1 file changed, 9 insertions(+), 8 deletions(-)

(limited to 'greedy/main.tex')

diff --git a/greedy/main.tex b/greedy/main.tex
index def9d8e..e8fe309 100644
--- a/greedy/main.tex
+++ b/greedy/main.tex
@@ -119,7 +119,7 @@ often leads to treating them as ``discrete concave functions''.
 
 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
+``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}
@@ -216,9 +216,10 @@ is considered to have polynomial running time.
 \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.
+    \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}
@@ -355,7 +356,7 @@ a constant approximation ratio to the optimal solution.
 \end{proof}
 
 \begin{remark}
-    \cite{lin2010} noted that the above analysis can be refined to show that
+    \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}
@@ -541,7 +542,7 @@ 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
+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.
@@ -553,8 +554,8 @@ continuous optimization. A combinatorial algorithm was later constructed by
 
 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}.
+results from the late 70's. A general framework to combine constraints can be
+found in \cite{vondrak2011}.
 
 \bibliographystyle{abbrvnat}
 \bibliography{sub}
-- 
cgit v1.2.3-70-g09d2

