From 1aec92a787374451c7757be86bd27ee4ac064c41 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Thu, 1 Nov 2012 17:01:27 +0100 Subject: Some typos --- main.tex | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'main.tex') diff --git a/main.tex b/main.tex index 53de028..cfb7799 100644 --- a/main.tex +++ b/main.tex @@ -15,7 +15,6 @@ One possible interpretation of \eqref{modified} is that, prior to the auction, t \subsection{Truthful, Constant Approximation Mechanism} - In this section we present a mechanism for \EDP. Previous works on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and designing auction mechanisms for submodular utility functions \cite{singer-mechanisms, @@ -51,7 +50,7 @@ OPT(V,\mathcal{N},B) \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big) \end{lemma} Hence, taking the maximum between the greedy set and the point of maximum value -has an approximation ratio of $\frac{5e}{e-1}$. However, Singer +yields an approximation ratio of $\frac{5e}{e-1}$. However, Singer \cite{singer-influence} notes that this approach breaks incentive compatibility and therefore cannot be directly applied to the strategic case. -- cgit v1.2.3-70-g09d2