diff options
Diffstat (limited to 'greedy')
| -rw-r--r-- | greedy/main.tex | 17 |
1 files changed, 9 insertions, 8 deletions
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} |