muthu

1 files changed, 33 insertions, 17 deletions

diff --git a/main.tex b/main.tex
index 4fa6e74..482b1c9 100644
--- a/main.tex
+++ b/main.tex
@@ -1,10 +1,16 @@
-
+\label{sec:main}
 %\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 value functions \cite{singer-mechanisms,
-chen, singer-influence} rely on a greedy algorithm. In this algorithm, elements
+In this section we present a mechanism for \EDP.
+
+\paragraph{Prior approach on sub modular optimization, without strategy} 
+ Previous works~\cite{nemhauser, sviridenko-submodular,singer-mechanisms,chen, singer-influence}
+%
+%on maximizing submodular functions \cite{nemhauser, sviridenko-submodular} and designing
+%auction mechanisms for submodular value functions \cite{singer-mechanisms,
+%chen, singer-influence} 
+%
+rely on a greedy algorithm. In this algorithm, elements
 are added to the solution set according to the following greedy selection rule.
 Assume that $S\subseteq \mathcal{N}$ is the solution set constructed thus far; then, the next element $i$ to be
 included in $S$ is the one with the highest \emph{marginal-value-per-cost}:
@@ -14,36 +20,46 @@ included in $S$ is the one with the highest \emph{marginal-value-per-cost}:
 This process terminates when no more items can be added to $S$ using \eqref{greedy} under budget $B$. This is the generalization of the \emph{value-per-cost} ratio used in the greedy approximation
 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 it the element is added.
-
+%
 Unfortunately, even for the full information case, the greedy algorithm gives an
 unbounded approximation ratio. 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
+= \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. In the general case, we have the
+gives a $\frac{2e}{e-1}$ approximation ratio ~\cite{khuller} . In the general 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}[Singer \cite{singer-influence}]\label{lemma:greedy-bound}
-Let $S_G$ be the set computed by the greedy algorithm and define $i^*$:
-\begin{displaymath}
-    i^* = \argmax_{i\in\mathcal{N}} V(i)
-\end{displaymath}
-then the following inequality holds:
+\begin{lemma}~\cite{singer-influence}\label{lemma:greedy-bound}
+Let $S_G$ be the set computed by the greedy algorithm and let 
+%define $i^*$:
+%\begin{displaymath}
+$i^* = \argmax_{i\in\mathcal{N}} V(i).$
+%\end{displaymath}
+We have:
+% the following inequality holds:
 \begin{displaymath}
 OPT \leq \frac{e}{e-1}\big( 3 V(S_G) + 2 V(i^*)\big).
 \end{displaymath}
 \end{lemma}
 
 Hence, taking the maximum between $V(S_G)$ and $V(i^*)$ yields an approximation
-ratio of $\frac{5e}{e-1}$. However, Singer \cite{singer-influence} notes that
+ratio of $\frac{5e}{e-1}$. However, 
 this approach breaks incentive compatibility and therefore cannot be directly
-applied to the strategic case. Indeed, suppose this allocation mechanism is used, and consider a case where
+applied to the strategic case.~\cite{singer-influence}
+\junk{
+Indeed, suppose this allocation mechanism is used, and consider a case where
 the allocates  the greedy set ($V(S_G) \geq V(i^*)$). If an
 agent $i$ from $S_G$ reduces her cost, it could happen that $V(S_G)$
 becomes smaller than $V(i^*)$. In this case the mechanism's allocation becomes
 $i^*$, and $i$ is excluded from the allocated set. This violates the monotonicity of
 the allocation function and hence also truthfulness, by Myerson's Theorem.
+}
+
 
 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