summaryrefslogtreecommitdiffstats
path: root/main.tex
diff options
context:
space:
mode:
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.