diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 4 |
1 files changed, 1 insertions, 3 deletions
@@ -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. |
