removed erroneous statement

1 files changed, 29 insertions, 8 deletions

diff --git a/main.tex b/main.tex
index dd45e6d..65128b1 100644
--- a/main.tex
+++ b/main.tex
@@ -21,22 +21,25 @@ This process terminates when no more items can be added to $S$ using \eqref{gree
 algorithm for \textsc{Knapsack}. However, in contrast to \textsc{Knapsack}, for general submodular
 functions, the marginal value  of an element in \eqref{greedy} depends on the set to which the element is added.
 Similarly, the value of an element depends on the set in which it is
-considered. However, in the following, the value of an element $i$ will refer to
-its value as a singleton set: $V(\{i\})$. If there is no ambiguity, we will write
-$V(i)$ instead of $V(\{i\})$.
-
+considered. 
+%However, in the following, the value of an element $i$ will refer to
+%its value as a singleton set: $V(\{i\})$. If there is no ambiguity, we will write
+%$V(i)$ instead of $V(\{i\})$.
 Unfortunately, even for the full information case, the greedy algorithm gives an
-unbounded approximation ratio. Let  $i^*
+unbounded approximation ratio. Instead, we have:
+\junk{
+ Let  $i^*
 = \argmax_{i\in\mathcal{N}} V(i)$ be the element of maximum value.
 % (as a singleton set).
 %It has been noted by Khuller \emph{et al.}~\cite{khuller} that 
- For the maximum
-coverage problem, taking the maximum between the greedy solution and $V(i^*$)
-gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller}. In the general case, 
+For the maximum
+coverage problem, taking the maximum between the greedy solution and $V(i^*)$ (shorthand for $V(\{i\})$)
+gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller}. In the general sub modular case, 
 \junk{we have the
 following result from Singer \cite{singer-influence} which follows from
 Chen \emph{et al.}~\cite{chen}: \stratis{Is it Singer or Chen? Also, we need to introduce $V(i)$ somewhere...}
 }
+}
 
 \begin{lemma}~\cite{singer-influence}\label{lemma:greedy-bound}
 Let $S_G$ be the set computed by the greedy algorithm and let 
@@ -64,7 +67,24 @@ $i^*$, and $i$ is excluded from the allocated set. This violates the monotonicit
 the allocation function and hence also truthfulness, by Myerson's Theorem.
 }
 
+For the strategic case, 
+\begin{itemize}
+\iem
+When the underlying
+full information problem \eqref{eq:non-strategic} can be solved in
+polynomial time, Chen et al. \cite{chen} prove that  
+%$OPT_{-i^*}$, the optimal solution to \eqref{eq:non-strategic} when $i^*$ is excluded from set $\mathcal{N}$, can play the %role of this quantity: that is, 
+allocating to $i^*$ when
+$V(i^*) \geq C\cdot OPT_{-i^*}$ (for some constant $C$)
+and to $S_G$ otherwise yields a 8.34-approximation mechanism. However, this is not a poly-time mechanism when the underlying problem is NP hard (unless P=NP), as is the case for \EDP.
 
+\item
+
+
+\end{itemize}
+
+
+\junk{
 To address this, Chen \emph{et al.}~\cite{chen} %and Singer~\cite{singer-influence},
  introduce a third quantity: if $V(i^*)$ is larger than this quantity, the
 mechanism allocates to $i^*$, otherwise it allocates to the greedy set $S_G$.
@@ -79,6 +99,7 @@ full information problem \eqref{eq:non-strategic} can be solved in
 polynomial time, Chen et al. \cite{chen} prove that  $OPT_{-i^*}$, the optimal solution to \eqref{eq:non-strategic} when $i^*$ is excluded from set $\mathcal{N}$, can play the role of this quantity: that is, allocating to $i^*$ when
 $V(i^*) \geq C\cdot OPT_{-i^*}$ (for some constant $C$)
 and to $S_G$ otherwise yields a 8.34-approximation mechanism. However, this is not a poly-time mechanism when the underlying problem is NP hard (unless P=NP), as is the case for \EDP.
+}
 
 \fussy
 For  NP-hard