summaryrefslogtreecommitdiffstats
path: root/main.tex
diff options
context:
space:
mode:
authorStratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>2013-02-11 19:29:32 -0800
committerStratis Ioannidis <stratis@stratis-Latitude-E6320.(none)>2013-02-11 19:29:32 -0800
commitfca9d9fca8141e104b792ce0b27346d83af71b82 (patch)
tree8d7969ccd5ce8f58d1ea6b10f21a569c00176853 /main.tex
parentfcb7ef2df7ddd557ae689f79f32498dd2c705c01 (diff)
downloadrecommendation-fca9d9fca8141e104b792ce0b27346d83af71b82.tar.gz
small changes
Diffstat (limited to 'main.tex')
-rw-r--r--main.tex4
1 files changed, 1 insertions, 3 deletions
diff --git a/main.tex b/main.tex
index fa8558e..469995d 100644
--- a/main.tex
+++ b/main.tex
@@ -23,7 +23,7 @@ the following algorithm:
\textbf{if}\; V(\{i^*\}) \geq V(S_G)\; \textbf{return}\; \{i^*\}
\;\textbf{else return}\; S_G
\end{equation}
-has an approximation ratio of $\frac{5e}{e-1}$ \cite{chen}.
+has a constant approximation ratio \cite{singer-mechanisms}.
\subsection{Submodular Maximization in the Strategic Case}
@@ -146,8 +146,6 @@ We can now state our main result:
\end{theorem}
The value of the constant $C$ is given by \eqref{eq:constant} in
Section~\ref{sec:proofofmainthm}.
-
-\fussy
In addition, we prove the following simple lower bound.
\begin{theorem}\label{thm:lowerbound}
There is no $2$-approximate, truthful, budget feasible, individually rational mechanism for EDP.